Министерство образования и науки Российской Федерации
Севастопольский государственный университет
МЕТОДИЧЕСКИЕ УКАЗАНИЯ
по выполнению лабораторных работ по дисциплине
«Теория принятия решений»
для студентов очной и очно-заочной форм обучения по направлению 09.03.02
«Информационные системы и технологии»
Севастополь
2019
2
УДК 519.2
Методические указания по выполнению лабораторных работ по дисциплине «Теория
принятия решений» для студентов очной и очно-заочной форм обучения по направлению
09.03.02 «Информационные системы и технологии». /Сост. К.В.Кротов. – Севастополь: Изд-во
СевГУ, 2019. – 90 с.
Методические указания составлены в соответствии с требованиями рабочей программы
дисциплины «Теория принятия решений» для студентов направления 09.03.02 и утверждены на
заседании кафедры информационных систем, протокол № 10 от 24 мая 2019 года.
Допущено учебно-методическим центром СевГУ в качестве методических указаний.
Рецензент: Шевченко В.И. , кандидат технических наук, доцент кафедры Информационных
технологий и компьютерных систем
3
СОДЕРЖАНИЕ
Общие требования к выполнению лабораторных работ…………………….……………………..4
1. Лабораторная работа №1. Исследование применения аппарата бинарных отношений для
решения задачи выбора альтернатив……………………………………...………………………...5
2. Лабораторная работа №2. Исследование применения аппарата теории одномерной
полезности для решения задач выбора альтернатив…………………………………………..…17
3. Лабораторная работа №3. Исследование применение аппарата многомерной полезности для
принятия решений…………………………….…………………………. ………………………...28
4. Лабораторная работа №4. Исследование методов решения многокритериальных задач принятия
решений на основе построения множества Парето………….……………….…….….39
5. Лабораторная работа №5. Исследование применения теории важности критериев для
решения задачи выбора альтернатив……………………………………………………….….…..53
6. Лабораторная работа №6. Исследование применения метода анализа иерархий для решения
задачи выбора альтернатив……………………………………………………………….…….…..71
7. Лабораторная работа №7. Исследование методов группового выбора при принятии
решений………………………………………………………………………………….…………..81
Библиографический список…………………………………………………………………..…....90
Приложение А………………………………………………………………………………….……91
4
ОБЩИЕ ТРЕБОВАНИЯ К ВЫПОЛНЕНИЮ ЛАБОРАТОРНЫХ РАБОТ
1. ЦЕЛЬ И ЗАДАЧИ ЛАБОРАТОРНЫХ РАБОТ
Цель настоящих лабораторных работ состоит в исследовании методов теории принятия
решений для реализации задач выбора эффективных альтернатив в различных предметных
областях. Задачами выполнения лабораторных работ являются: 1) углубленное изучение
основных теоретических положений дисциплины; 2) получение практических навыков
написания программ, реализующих методы теории принятия решений.
2. ОПИСАНИЕ ЛАБОРАТОРНОЙ УСТАНОВКИ
Объектом исследования в лабораторных работах являются методы и алгоритмы решения
задач теории принятия решений, реализации методов с использованием современных
программных средств. Инструментом исследования методов и алгоритмов теории принятия
решений является ЭВМ. Программным средством исследования является язык С++, для
разработки программ используется среда Visual studio. Выполнение работы предусматривает
создание проекта в среде Visual studio, разработку и отладку программы на языке C++ на
основе методов и алгоритмов теории принятия решений, рассматриваемых в данных
методических указаниях.
3. СОДЕРЖАНИЕ ОТЧЕТА
Отчеты по лабораторной работе оформляются каждым студентом индивидуально. Отчет
должен включать: название лабораторной работы; цель работы; краткие теоретические
сведения; постановку задачи; текст программы, реализующей задание; распечатку результатов
выполнения программы.
4.ЗАДАНИЕ НА РАБОТУ
Задание выбирается в соответствии с вариантом, назначаемым преподавателем.
5
ЛАБОРАТОРНАЯ РАБОТА №1
ИССЛЕДОВАНИЕ ПРИМЕНЕНИЯ АППАРАТА БИНАРНЫХ ОТНОШЕНИЙ ДЛЯ
РЕШЕНИЯ ЗАДАЧИ ВЫБОРА АЛЬТЕРНАТИВ
1. Цель работы: исследовать применение аппарата бинарных отношений при принятии
решений по выбору альтернатив
2. Теоретическое введение
2.1. Общие понятия бинарных отношений
Бинарные отношения – это отношения, которые могут выполняться или не
выполняться между элементами одного множества. Если X –– множество решений
(альтернатив), тогда отношение R на множестве X - это подмножество R X * X , т.е. R -
множество пар (xi , x j ) , определѐнные на декартовом произведении X * X ( X 2 ), для которых
выполняется определѐнное (заданное) свойство.
Обозначение для отношения R .
Если пара (xi , x j ) R , то xi Rx j ( xi находится в отношении R с
x
j
). Множество
X –
область задания отношений (отношения R ).
Способы задания отношений:
1. Задание матрицей. Если множество X состоит из n элементов, то элементы xi
X
могут быть проидентифицированы индексами i такими, что i
; тогда для решений xi
X
1, n
может быть введена в рассмотрение матрица A размерности n n .
При этом если
xi Rx j , то, aij=1; если xi Rx j не является верным
(т.е.
(xi , x
j )

R ), то
aij=0, тогда общее правило определения элементов матрицы A следующее ( (aij
)A):
1, если xi Rx j
;
aij ( A )
не верно;
0,
если xi Rx
j
при этом i
1, n
;
j
1, n
.
Пример 1. Задание вида матрицы A ( при n 4 ).
1
2
3
4
1
0
1
1
0
A 2
1
0
1
0
3
0
0
0
0
4
0
0
0
0
Заметим, что aii=0, (т.е. в данном (общем) рассматриваемом случае ( xi , xi ) R ).
2. Задание графом. Графом G называется пара G( X , Г ) , где X – конечное множество
вершин, Г (гамма) – конечное подмножество произведения X 2 , множество дуг, соединяющих
вершины; дугу, соединяющую вершину xi с вершиной x j , обозначим как ( xi , x j ) .
Если множество решений (альтернатив) X однозначно соответствует множеству вершин
графа X , тогда дуга (xi , x j ) соединяет две вершины xi и x j в том случае, если
выполнено отношение xi Rx j .
6
Если задан граф G с n вершинами (где
X
n ), нумерация вершин G соответствует
нумерации решений (альтернатив) из X , тогда на графе G (для элементов множества X )
задаѐтся отношение R такое, что при xi Rx j на графе определяется дуга (формируется дуга)
(xi , x j ) .
Пример 2. Задание графа отношения G(R) (Рисунок 1).
x1 x1
x2
x3
x2
x
3
а) б)
Рисунок 1 – Виды графов отношений G(R)
3. Задание сечением. Верхнее сечение множества (отношения) R обозначается как R
(xi ) (т.е. определяется для каждого элемента xi множества X ) и формируется в
соответствии с выражением вида:
(x
i
, x
j
) R : R
(x
j
)

x
i
 X
xi Rx j.
Если R – отношение предпочтения (доминирования), то для элемента
x j верхнее сечение
R (x j ) отношения R – это те решения xi , которые предпочтительнее,
чем рассматриваемое
решение xi . Нижнее сечение отношения R определяется аналогичным образом:
( xi , x
j ) : R
( xi )


x
j
∈
X
xi Rx j
Таким образом, R (x j ) – те элементы (решения) xi , которые находятся с элементом x j в
отношении R ; R ( xi ) – те элементы X (решения x j ), с которыми фиксированный элемент xi
находится в отношении R .
Отношения специального вида.
1. Пустое отношение. Отношение называется пустым Ø, если оно не выполняется ни для
одной пары ( xi ,x j ) X 2 . Тогда матрица A( Ø ) такая, что aij ( Ø ) 0 для всех i , j граф G( Ø )
не имеет дуг, сечения R (x) R (x) Ø.
2. Полное отношение. Отношение называется полным, если оно выполняется для всех пар ( xi
,x j ) X 2 . Полное отношение обозначается Р. Тогда A(P) такая, что aij (P) 1 для всех
индексов i , j ; граф G(P) такой, что дуги соединяют любую пару вершин; R (x) R (x) X
\x для любого x X .
Операции над отношениями.
1. Вложение отношений. Отношение R1 вложено или включено в отношение R2 (обозначается
R2 R1 ), если множество пар (xi , x j ) , для которых выполнено отношение R1 , содержится в
множестве пар, для которых выполнено отношение R2 . Если R2 R1 , то либо R2 R1 , либо
R2 R1.
7
2. Дополнение отношения R . Отношение R называется дополнением отношения R , если оно
выполняется для тех пар (xi , x j ) , для которых не выполняется отношение R . Таким образом,
если (xi , x j ) R , то (xi , x j ) R (т.е. R X \ R ). Тогда aij (R) 1 aij (R) , граф G(R) содержит
те дуги, которые отсутствуют в графе G(R) .
3. Обратное отношение. Обратным к отношению R называется отношение R1 , определяемое
условием:
x R
1
x
j

x
Rx .
i
j
i
Если R –
отношение «меньше» на
множестве
действительных чисел, то обратное
отношение
R
1
– «больше». Для обратного отношения справедливо:
1) a
( R1 ) a
( R ) при i
, j
;
ji
1, n
1,
n
ij
2) граф G(R1 ) получается из графа G(R) изменением направления дуг.
Свойства отношений
1. Рефлексивность. Отношение R называется рефлексивным, если xi Rxi . Тогда:
а) в матрице A(R) рефлексивного отношения R на главной диагонали заданы 1; б)
в графе G(R) при каждой вершине имеется петля.
Соответственно, если отношение R антирефлексивно, то выражение вида xi Rxi не является
верным, в этом случае диагональные элементы матрицы A(R) равны 0.
2. Симметричность. Отношение R - симметрично, если из xi Rx j вытекает x j Rxi . Тогда:
а) матрица A(R) отношения R симметрична, т.е. aij a ji .
б) каждая вершина xi графа G(R) имеет исходящую дугу ( xi , x j ) и входящую дугу ( x j , xi ) .
3. Асимметричность. Для пары ( xi , x j ) выполняется либо xi Rx j , либо x j Rxi , т.е. если xi Rx j
выполняется, то x j Rxi нет. В этом случае граф G(R) не может содержать одновременно дуги (
xi , x j ) и ( x j , xi ) (содержит одну из этих дуг).
4. Антисимметричность. Для антисимметричного отношения R выражения xi Rx j и x j Rxi
справедливы тогда, когда xi x j . Для антисимметричного отношения R граф G(R) не может
одновременно содержать дуги ( xi , x j ) и ( x j , xi ) при i j .
5. Транзитивность. Из xRz и zRy следует xRy .
6. Ацикличность. Из xi Rx j , x j Rxk ,…, xkl Rxm следует, что xi xm (т.е. путь на графе не
является циклом).
Виды отношений, используемых в ТПР
1. Отношение эквивалентности ~ (вид отношения, связывающего пару решений (xi , x j ) –
( xi ~ x j ) . Свойства
транзитивно ( xi ~ x j ,
отношения: рефлексивно (xi ~ xi ), симметрично ( xi ~ x j и x j ~ xi ) ,
x j ~ xk , xi ~ xk ) . Отношение эквивалентности ~ определяет, что два
решения
xi
и
x j
эквивалентны.
2. Отношение нестрогого предпочтения xi x j определяет, что решение xi не хуже, чем
решение x j (т.е. лучше или эквивалентно). Таким образом для пары решений выполняется
либо xi x j либо xi ~ x j . Свойства отношения: рефлексивность ( xi xi ), антисимметричность
(если xi x j и x j xi , то xi ~ x j ), транзитивность (если xi x j и x j xk , то xi xk ). Таким образом,
отношение позволяет реализовывать упорядоченность решений при возможной их
эквивалентности. Отношение нестрогого предпочтения индуцирует отношение нестрогого
(частичного) порядка на множестве X.
8
3. Отношение строгого предпочтения xi x j (т.е. решение xi строго лучше, чем x j ).
Свойства отношения: антирефлексивность ( xi x j не является верным), антисимметричность
(если верно xi x j , то x j xi
- не
верно и наоборот). Отношение
также соответствует
отношению строгого предпочтения
(доминирования). Т.е. при xi
x j
решение xi строго
предпочтительнее решения x j ,
решение xi доминирует решение
x j .
Отношение строгого
предпочтения индуцирует отношение строгого порядка на множестве решений X.
Тогда с использованием отношений и ~ может быть определѐн порядок
(предпочтительность, доминирование) решений.
Пример 3. Задание вида порядка решений.
xi x j ~ xk xl
2.2. Выбор эффективных решений, порождѐнный бинарными отношениями
Если X - множество решений, тогда в нѐм может быть определено подмножество С( X )
решений, называемых предпочтительными элементами (решениями) в X . Для определения в
множестве X подмножества С( X ) в рассмотрение введена функция отображения С ,
составляющая множеству X его подмножество С(X ) , т.е. С : X C(X ) .
Функция выбора – это способ построения подмножества предпочтительных решений
С ( X ) на основе множества решений X . Если на множестве решений X определено (задано)
бинарное отношение R (в частности, отношение строгого предпочтения ), то этому отношению
может быть поставлена в соответствие функция выбора С . Тогда с использованием функции
выбора на основе бинарного отношения R ( ) может быть определено множество
предпочтительных решений.
В случае, если для каждой пары
(x , x
j
)X2
выполнено (задано)
отношение R (т.е.
i
задано
xi Rx j ,
xi x j ),
тогда при определении
подмножества
C( X )⊆X могут быть
использованы следующие рассуждения:
1)
если
x
i
x
j
,
то при
определении
выбора решения xi , x j X
из
X считается, что
x j
С(X) ;
2) если xi x j , то xi может быть включено в С( X ) .
Если– отношение предпочтения
(
x
i
x
j
,
x
i
предпочтительнее
x
j ),
- отсутствие
предпочтения ( xi
x j , xi не предпочтительнее
x
j ), тогда из отношения
(
x
i
x j )
вытекают
два способа формирования множества С( X ) .
Первый способ.
Множество С R ( X ) образуется
теми
решениями xi , для
которых
условие
предпочтительности ими других решений (решений x j ) не выполняется (т.е.
x
j
x
не
предпочтительнее решений xi ∈C R ( X ) ).
Данная формулировка может быть представлена
следующим выражением:
С
R
( X )


x
i
X
x
j
 X , x
j
xi.
(1)
Тогда С R ( X ) - это те решения xi ,
для которых все возможные решения
x
j
X
не
предпочтительнее их.
Второй способ.
Решения
x
i
, формирующие С
R
( X ) , предпочтительнее любого решения
x
j

X
.
Данная формулировка формализована в виде выражения:
С
R
( X )


x
i
∈
X
∀
x
j
∈
X , x
i
x
j

.
(2)
9
Условие для определения С R ( X ) называется условием блокировки, условие для
определения СR ( X ) - условие предпочтения.
Таким образом, решения xi , входящие в множество С R ( X ) или СR ( X ) , определяемые
выражениями (1), (2), являются наилучшими решениями, т.к. они непосредственно
доминируют (являются предпочтительными) остальные решения x j либо не доминируются ни
одним из решений x j .
Пример определения наилучших (предпочтительных) решений на основе графовой
модели представления бинарных отношений приведѐн на Рисунке 2.
а) б)
Рисунок 2 – Вид графовой моделей для определения наилучших
(предпочитаемых) решений
На Рис. 2а) решение x1 является предпочитаемым так как оно домирирует оставшиеся
решения x2 и x3. На Рис. 2б) решение x3 является предпочитаемым, т.к. оно не диминируется
ни одним из решений, входящих в множество Х. Определение предпочтительных решений xi
∈X , доминирующих остальные решения множества X , на основе графовых моделей
рассмотрено ниже.
Альтернативный вариант графа отношения строго предпочтения представлен на Рисунке
3.
Рисунок 3 – Вид графовой модели отношения, для которой не
выполняются условия для наилучший решений
На Рис.3 решения x6 и x7. являются не сравнимыми и они не доминируются ни одним
другим решением из множества Х .
В случае, если для множества X не может быть сформировано множество
предпочитаемых решений, то для этого множества может быть сформировано множество
максимальных элементов обозначенное как MaxR X , среди которых могут быть выбраны
эффективные решения. Для включения элемента (решения) xi множества X (xi X ) в
множество максимальных элементов MaxR X (где R - отношение
предпочтения/доминирования ) должно выполняться одно из следующих условий:
10
1)x j : xi x j ( xi предпочтительнее x j для всех x j ), тогда если элемент x j доминируем , то он
не включается в MaxR X ;
2) решения xi и x j эквивалентны ( xi ~ x j ) и решение xiMax R X ;
3) решения xi и x j не сравнимы.
Реализация второго условия предполагает, что для пары элементов (xi , x j ) R между
вершинами имеются две разнонаправленные стрелки. Реализация третьего условия предполагает, что
решения x
i
и
x
j
не связаны отношением предпочтения (т.е. не сравнимы), тогда между ними
нет стрелки на графе G(R) ;
Тогда xi X является максимальным элементом в модели X , R если:
x
j
X : (xi , x j ) R (x j , xi ) R .
Таким образом, основное понятие для принятия решений с использованием бинарного
отношения
предпочтения–
это максимальный элемент и множество максимальных
элементов
MaxR X . Тогда формирование множества
MaxR X
– это выделение наилучших
элементов
x X по бинарному отношению .
i
Определение. Множество
MaxR X называется внешне устойчивым, если для любого
элемента
x
j
∈
X \ Max
R
X
найдется такой элемент
x
i
∈
Max
R
X
, что x
i
Rx
j
.
Если
множество
MaxR X
внешне устойчиво,
то выбор эффективных решений xi
производится только в пределах
MaxR X . Множество
MaxR X
называется ядром множества
X .
Тогда под задачей принятия решений с использованием бинарных отношений
подразумевается задача выделения ядра MaxR X
из множества
X . На Рис. 3 множество
MaxR X имеет вид:
MaxR X


x6 , x7

, но при этом оно не является внешне устойчивым, т.е. в
нем не могут быть выбраны эффективные решения.
Особенности
построения
алгоритма формирования
множества
Max
R
Xдалее
прокомментированы на примерах.
Пример 4. Вид графа G(R)
и матрицы отношения (Рис. 4).
x4
x5
x
1
x
2
x
3
x
4
x
5
x1
0
0
1
0
0
x3
(a
ij
)
x
2
0
0
1
0
0
x3
0
0
0
1
1
x4
0
0
0
0
0
x1
x2
x5
0
0
0
0
0
Рисунок 4 – Вид графовой модели и матрицы отношений, для которых
формируется множество MaxR X
Матрица (aij ) отображает непосредственное предпочтение решения xi над решением
x j (xi Rx j ) .
Так как элементы xi строго упорядочены с точки зрения отношения , то aij ≠a ji
.
Решения x1 и x2 доминируют все остальные решения (предпочтительнее всех остальных
решений) поэтому в столбцах j1 , j 2 a 0 для всех i .
ij
11
Для рассматриваемого примера синтаксис определения состава множества MaxR X (в
рассмотрение введен массив MaxR) имеет следующий вид:
Цикл i=1 до 5
MaxR[i]=1;
Цикл j=1 до 5
Цикл i=1 до 5
Если a[i,j]=1 то
MaxR[j]=0;
Пример 5. Вид графа G(R) и матрицы парных сравнений для отношения (Рисунок 5).
x 4
x5
x1
x
2
x
3
x
4
x
5
x1
0
0
1
0
0
x3
(a
ij
)

x
2
0
0
1
0
0
x3
0
1
0
1
1
x1
x2
x4
0
0
1
0
0
x5
0
0
0
0
0
Рисунок 5 – Вид графовой модели и матрицы отношений, для
которых формируется множество MaxR X
Предлагаемый код программы для формирования множества MaxR X (вектора MaxR)
следующий:
Цикл i=1 до 5
MaxR[i]=1;
Цикл i=1 до 5
Цикл j=1 до 5
Если a[i,j]=1 то
Если a[j,i]=0 то
MaxR[j]=0;
Если (a[j,i]=1)( MaxR[i]=0) то
MaxR[j]=0;
Подобный синтаксис определения элементов множества MaxR X (массива Max _ X )
может быть применен и для вида графа G(R) в Примере 6 (Рисунок 6).
Пример 6. Вид графа G(R) бинарных отношений для множества решений Х.
x4 x5
x3
x1 x2
Рисунок 6 – Вид графовой модели отношений, для которой
формируется множество MaxR X
12
Понятно,
что в результате должно быть получено множество
MaxR X
в виде:
MaxR X
{x1
x
2
}
. Таким образом условиями включения/не включения элемента
xi ∈X
в
множество MaxR X являются:
1) xi x j x j MaxR X ;
2) еслиx j : xi x j xi MaxR X ;
3) если xi x j x j xi xi MaxR X и x j ∈MaxR X при условии, что ни xi ни xj не доминируются.
Задание. Выполнить проверку применимости приведенного программного кода для
графов отношений следующего вида (Рис.7).
x4 x5
x3
x1
x2
а)
б)
Рисунок 7– Виды графовых моделей отношений, для
которых формируются множества MaxR X
2.3.Определение порядка решений для графовых моделей бинарных отношений
Бинарные отношения между решениями могут быть представлены в виде графовой
модели G(R) , дуги на графе соединяют вершины x и x если бинарное отношение
i j
R связывает решения
xi
и
x j .
Задание. На графе G(R) , определяющем бинарные отношения и представленным на Рис.8,
идентифицировать сравнимые и несравнимые решения.
x3
x4
x1
x2
x6 x7
x5
Рисунок 8 – Вид графовой модели G(R) бинарных отношений
Если граф не содержит контуров, то все его вершины могут быть упорядочены таким
образом, что направления всех дуг будут совпадать. В результате вершины графа G(R)
(решения xi ) могут быть распределены по ярусам. В вершины x j яруса k входят дуги из
вершин xi ( k1 )-го яруса если xi Rx j , из вершин x j k-го яруса вы ходят дуги в вершины xh
13
( k + 1) -го яруса в том случае, если x j Rxh . Формирование распределения вершин xi по ярусам
для графовой модели G(R) позволяет определить порядок этих вершин (порядок решений) и,
соответственно, выделить лучшие решения. Для определения порядка (упорядочивания)
решений (вершин графа G(R) ) может быть реализован следующий алгоритм. На i-ой
итерации алгоритм реализует выделение вершин источников (т.е.вершин. в которые не входят
стрелки). Решения, соответствующие этим вершинам, ставятся на i-е место в
последовательности решений П , после чего выбранные вершины отбрасываются.
Обобщенный порядок шагов алгоритма, реализующего определение последовательности
решений с точки зрения бинарного отношения предпочтения, следующий:
1) i1 ;
2) выбрать варианты–источники (вершины, решения). Если таковые отсутствуют – переход на
шаг 7;
3) выбранные вершины отнести к i -ому ярусу;
4) i = i + 1;
5) выбранные на втором шаге вершины – источники удаляются из графа (в дальнейшем не
рассматриваются);
6) переход к шагу 2;
7) конец.
Пример реализации данного алгоритма ориентирован на работу с матрицей
инциденций. Элемент матрицы (aij ) 1 в случае, если из вершины xi в вершину x j идет
направленная дуги. Если вершина является источником, то отсутствуют дуги, идущие в неѐ.
Тогда весь j -ый столбец, соответствующий вершине-источнику xi , должен содержать нулевые
элементы (т.к. данная вершина не зависит от других и в неѐ не ведут дуги).
Реализацию алгоритма построим на примере графа G(R) , представленного на Рис. 9, и
соответствующей ему матрицы инциденций.
x5
x4
x1
x2
x
3
x
4
x
5
x1
0
1
1
0
0
a
ij
x
2
0
0
1
1
0
x3
0
0
0
1
1
x3
x2
x4
0
0
0
0
0
x5
0
0
0
0
0
x1
Рисунок 9 – Вид графовой модели G(R) бинарных отношений и
соответствующая ей матрица отношений
В результате реализации приведенного фрагмента программы все решения будут
упорядочены, при этом лучшее решение будет являться первым в массиве MaxR.
Аналогичный подход может быть реализован и при анализе вершин-приемников, т.е
вершин, в которые идут стрелки. Тогда самыми первыми в упорядоченном массиве решений
MaxRбудут являться те вершины, из которых не выходят стрелки, а самым лучшим решением
в их последовательности будет являться последнее решений.
//Обозначение параметров, используемых при реализации алгоритма
// К - количество элементов, добавленных в массив Max[i]
// MaxR [ i ] - массив решений, упорядоченных с точки зрения убывания предпочтения
14
// счѐтчик – текущее количество решений, которые могут быть проанализированы
Счѐтчик =5; К =0; К1=1;
Пока счѐтчик >=0
// определение исключаемых элементов
Цикл j 1 до 5
Сумма =0;
Цикл i1 до 5
Сумма=Сумма + a[i, j] ;
Если Сумма =0 то
К =К+1;
MaxR [ K ] = j ;
Цикл q = K1 до К
// обнуление элементов в aij , зависящих только от решений,
// находящихся в массиве MaxR.
Цикл j 1 до 5
a[ MaxR [ q ], j ] = 0 ;
// исключение элементов, добавленных в MaxR
Цикл q = K1 до К
Цикл i = 1 до 5
a[ j,MaxR [ q ]] = 1; ;
K1=K+1; Cчетчик=5-К;
Конец цикла пока;
3. Программа выполнения работы
3.1. Для Варианта 1 задания на работу, связанного с формированием подмножества
максимальных элементов MaxRмножества Х, необходимо по заданному варианту графа
отношений предпочтения между решениями сформировать матрицу А отношения R (где R–
отношение ). При этом убедиться, что первый элемент множества Х является строго
независящим от других решений.
3.2. Выполнить формирование множества MaxRвручную для заданного вида графа и
соответствующего ему вида матрицы А.
3.3. Выполнить формирование программного кода соответствующей процедуры определения
множества MaxR, при этом возможно руководствоваться ориентировочным видом процедуры
определения этого множества, предложенным в теоретическом введении данной лабораторной
работы.
3.4. Выполнить вывод результатов работы процедуры и сравнить полученные в процедуре
результаты с результатами, сформированными аналитически.
3.5. Изменить исходные данные программы, используя графы отношений из примера 5 (Рис
7). Проверить получаемые с использованием процедуры результаты с аналитическим
результатами, формируемыми для этих графов.
3.6. Варианты 2 и 3 задания на работу, связаны с построением упорядоченного множества
решений, формируемого на основе задаваемого множества Х и отношений между его
элементами, представленными в виде графа. Для реализации задания необходимо на основе
графа заданного вида сформировать матрицу А отношений между решениями xi .
3.7. Для полученного вида матрицы А аналитически выполнить определение порядка
решений– множества упорядоченных решений MaxR. Упорядочить рассматриваемые решения
по ярусам. Определить количество элементов на первом (либо последнем) ярусе формируемой
схемы, эти элементы (решения) являются эффективными.
15
3.8. В соответствии с предложенным возможным синтаксисом процедуры определения
упорядоченного множества решений MaxR выполнить формирование программы, которая в
соответствии с видом матрицы отношений А реализует определение множества MaxR.
Предусмотреть при написании программы указание номера яруса схемы, на котором
находятся соответствующие решения. Руководствуясь нумерацией ярусов определить
эффективные решения (на первом либо последнем ярусах).
3.9. Выполнить сравнение полученных с использованием процедуры результатов с
результатами, полученными аналитически.
3.10. Изменить в реализуемой программе исходные данные, изменив их на данные Рис.9.
Выполнить аналитическое построение множества MaxRдля этих данных и сравнить его с
результатами, полученными с использованием процедуры.
3.11. В отчете представить графы отношений между решениями в соответствии с вариантом
задания, виды матриц А отношений между решениями, аналитические виды решений
поставленной задачи, распечатки результатов решения задачи с использованием
разработанной программы.
4. Варианты заданий
Вариант 1. Выполнит разработку программы, реализующей определение множества
максимальных элементов M a x R,руководствуясь заданной формой графа отношений. При
разработке программы использовать приведенные в теоретическом введении правила
формирования множества MaxR. При разработке программы использовать следующий вид
графа отношений между решениями множества Х.
x5
x4 x6
x2
x3
x1
Применить разработанную процедуру к графам на Рис. 7.
Вариант 2. Выполнит разработку программы, реализующей определение
упорядоченного множества решений MaxR для множества Х, руководствуясь заданной формой
графа отношений. При разработке программы использовать приведенные в теоретическом
введении правила формирования множества MaxRс учетом рассмотрения вершин-источников
на каждом шаге алгоритма. При формировании упорядоченного множества решений
указывать номер яруса, на котором находятся решения. Определить эффективные решения.
При разработке программы использовать следующий вид графа отношений между решениями
множества Х.
x3
x4
x1
x
2
x6 x7
x5
Реализовать определение эффективных решений для графа на Рис.9.
16
Вариант 3. Выполнит разработку программы, реализующей определение
упорядоченного множества решений MaxR для множества Х, руководствуясь заданной формой
графа отношений. При разработке программы использовать приведенные в теоретическом
введении правила формирования множества MaxRс учетом рассмотрения вершин-приемников
на каждом шаге алгоритма (задача, обратная рассматриваемой для Варианта 2). При
формировании упорядоченного множества решений указывать номер яруса, на котором
находятся решения. Определить эффективные решения. При разработке программы
использовать вид графа отношений между решениями множества Х, аналогичный варианту 2.
Реализовать определение эффективных решений для графа на Рис.9.
5. Контрольные вопросы.
5.1. Что такое бинарные отношения и что они характеризуют?
5.2. Каковы способы задания бинарных отношений?
5.3. Каковы свойства бинарных отношений и операции над ними?
5.4. Что такое функция выбора для предпочитаемых элементов и каким образом выбор
предпочитаемых элементов формализуется?
5.5. Что такое условия блокировки и предпочтения и как они формализуются?
5.6. Что такое наилучшие элементы множества решений и каким образом реализуется из
определение?
5.7. Что такое подмножество максимальных элементов MaxR X в множестве решений Х и
каковы условия принадлежности решения этому множеству?
5.8. Что такое внешняя устойчивость множества MaxR X и как она определяется (каковы
условия внешней устойчивости множества MaxR X )?
5.9. Какой вид может иметь примерный синтаксис программы определения элементов в MaxR
X при выполнении условия эквивалентности (несравнимости) решений?
5.10. Какие условия для вершин графа G(R) должны выполняться, чтобы решения могли быть
упорядочены?
5.11. Что из себя представляет алгоритм упорядочивания решений при рассмотрении вершин-
источников на графе G(R) ?
5.12. Что из себя представляет алгоритм упорядочивания решений при рассмотрении вершин-
приемников на графе G(R) ?
5.13. Какой вид имеет примерный синтаксис программы для упорядочивания решений при
рассмотрении вершин-источников на графе G(R) ?
5.14. Какой вид имеет примерный синтаксис программы для упорядочивания решений при
рассмотрении вершин-приемников на графе G(R) ?
5.15. Каким образом будут сформированы (какой вид имеют) множества MaxR X для графов
отношений G(R) на Рис.7?
5.15. Каким образом будут сформированы (какой вид имеют) упорядоченное множество
решений для множества Х и для графа отношений G(R) на Рис.9?
17
ЛАБОРАТОРНАЯ РАБОТА №2
ИССЛЕДОВАНИЕ ПРИМЕНЕНИЯ АППАРАТА ТЕОРИИ ОДНОМЕРНОЙ ПОЛЕЗНОСТИ
ДЛЯ РЕШЕНИЯ ЗАДАЧ ВЫБОРА АЛЬТЕРНАТИВ
1. Цель работы: исследовать применение аппарата теории полезности при принятии
решений по выбору альтернатив
2. Теоретическое введение
Общие понятия теории полезности и связь полезности с бинарными отношениями
В основу использования теории полезности при принятии решений при полной
определенности положено утверждение о том, что каждой альтернативе (решению xi ) в
множестве возможных решений X может быть поставлено в соответствие некоторое значение
(значение функции полезности, соответствующее альтернативе). При этом для любых двух
альтернатив (решений) если одна из них предпочтительнее других (т.е. xi x j ), тогда
полезность одной альтернативы больше полезности другой альтернативы. Обозначим через
U( xi ) функцию полезности для решений множества X . В рассматриваемом случае
предполагается, что множество альтернатив X является счетным и конечным.
Таким образом, использование функции полезности предполагает определение числовых
значений, характеризующих решения, связанные отношением предпочтения. Т.е. значения
функции полезности U( xi ) и U ( x j ) вытекают из отношения предпочтения между
альтернативами xi и x j на множестве альтернатив X .
Если решение x характеризуется одним параметром, тогда сравнение решений
i
выполняется с использованием непосредственно отношения предпочтения, в результате для
каждого xi формируется единственное значение функции U( xi ) . Тогда предпочтение для
решений (отношение предпочтения для пары решений ( xi , x j )) может быть
охарактеризовано функцией полезности (предпочтение альтернатив может быть
охарактеризовано соотношением значений функции полезности U( xi ) ). В этом случае
эффективным решением x*i (эффективной альтернативой x*i ∈X ) является та альтернатива,
для которой выполняется условие вида:
x*i = arg max U (xi ).
1≤i≤N
В случае, когда альтернативы (решения) xi могут быть рассмотрены как системы
нескольких признаков (факторов, свойств, критериев), тогда общие предпочтения для
альтернатив (решений) могут быть представлены как системы предпочтений (как
совокупность предпочтений) по различным факторам. Таким образом, формируются
предпочтения для решений по каждому фактору (признаку, критерию), выраженные в виде
значений функции полезности U j ( xi ) , где j - индекс критерия (фактора), по которому
формируются предпочтения для решений xi ( j я функция полезности). Затем на основе
U j ( xi ) формируется система предпочтений по всем факторам (аддитивная функция
полезности). Использование аддитивной функции полезности для сравнения альтернатив xi
∈X предполагает, что полезность целого представлена в виде суммы полезностей частей
(определенных отдельных факторов).
Таким образом, в теории полезности рассматривается использование функции
полезности для идентификации эффективных среди решений, каждое из которых
характеризуется единственным параметром (фактором, критерием), а также для
идентификации эффективных решений, характеризующихся группой (совокупностью)
18
параметров (факторов, критериев). При этом для упорядочения решений используется
аддитивная функция полезности.
При определении функции полезности U( xi ) для альтернатив (решений) xi множества
X должны быть решены следующие вопросы:
1) существование функций полезности U ( x ) на множестве альтернатив, сохраняющих
(функции полезности сохраняют) упорядочение альтернатив (решений), основанное на
бинарном отношении строгого предпочтения;
2) способы определения значений функции полезности;
3) для аддитивной функции полезности должны быть введены условия для того, чтобы
функции полезности для нескольких факторов (аддитивные функции полезности),
сохраняющие упорядочение по бинарному отношению предпочтения, могут быть
представлены в виде комбинаций функций полезности отдельных факторов; в результате
должно быть определено, каким условиям должны удовлетворять предпочтения для того,
чтобы функция полезности, сохраняя упорядочивание альтернатив, была представлена в виде
комбинации (суммы) функций полезности отдельных факторов.
Таким образом, функция полезности – это некоторая числовая характеристика решения,
являющаяся вещественно значной, значения которой определяются для каждого решения xi в
соответствии с бинарным отношением строгого предпочтения (т.е. из xi x j ). При этом
функция полезности сохраняет порядок решений, такой же, какой был сформирован
бинарным отношением предпочтения (т.е. упорядочивающая альтернативы (решения) из
множества X таким же образом, как и бинарные отношения – бинарное отношение
предпочтения ).
Перед тем, как сформулировать условия, выполнение которых позволяет устанавливать
связь между альтернативами xi ∈X ( i1, n ) и соответствующими им значениями функции
полезности, необходимо напомнить основные сведения, касающиеся отношения безразличия ~
(эквивалентности). В первую очередь отношение ~ является отношением безразличия (в
общем случае) и лишь затем являются отношением эквивалентности (в частном случае). В
общем случае отношение безразличия ~ определятся как отсутствие предпочтений между
двумя решениями xi и x j , т.е.: xi ~ x j <=> ( xi x j и x j xi ) .
Отношение безразличия может быть определено в соответствии со следующими
предпосылками:
1) лицо, принимающее решения (ЛПР), рассматривая решения xi и x j , не видит между ними
разницы, т.е. решения являются эквивалентными, т.е. xi ~ x j (где ~ – отношение безразличия
(эквивалентности));
2) ЛПР не может
определить, какое из решений
xi
и
x j
является для него
более
предпочтительным (т.е. он не уверен в выборе решения
xi
или
x j
в качестве наиболее
предпочтительного),
в этом случае отношение ~ –
это
отношение
безразличия, а
сами
решения xi и x j являются несравнимыми (в смысле отношения строгого предпочтения ,т.е.
xi ~ x j ).
В общем случае отношение безразличия ~ может не быть транзитивным, т.е. из
несравнимости xi с x j и x j с xk не следует несравнимость xi с xk . Тогда из xi ~ x j и
x j ~ xk xi ~ xk . Однако, если рассматривать отношение ~ как отношение эквивалентности,
то свойство транзитивности отношений должно выполняться. Действительно, если xi ~ x j и
x j ~ xk (где ~ – отношение эквивалентности), то xi ~ xk . Т.к. в дальнейшем отношение ~ для
решений xi и x j рассматривается как эквивалентность, то предполагается его транзитивность.
Понятно, что из отношений и ~ вытекает отношение нестрогого предпочтения (т.е. xi x j
– решение xi не хуже решения x j ).
19
После уточнения рассматриваемых отношений , ~ и могут быть сформированы условия
существования функции полезности U( xi ) для решений xi множества X .
Условия, определяющие возможность сопоставления альтернативам xi и x j
соответствующих им значений U( xi ) и U ( x j ) , рассматриваемых как значения функции
полезности, формируются следующим образом:
1) конечность и счетность множества альтернатив X ; множество X является счетным, если
количество n элементов в нем является задаваемым и ограниченным;
2) отношение предпочтенияпозволяет реализовать слабое упорядочивание элементов xi
множества X ; если наряду с отношением , определенном на множестве X , на этом же
множестве определено отношение эквивалентности ~, то отношение позволяет на множестве
X определить слабый порядок элементов xi этого множества (решений x i ) с
учетом возможной эквивалентности между решениями xi , x j ∈X .
В случае выполнения введенных выше условий элементам xi , x j множества X
(решениям xi , x j ∈X ) могут быть поставлены в соответствие числа U( xi ) и U ( x j ) такие,
что:
xi x j <=> U ( xi ) > U ( x j ) ,
где числа U( xi ) полезности
множества Х).
, U ( x j ) могут быть проинтерпретированы как значения дискретной
функции (функции полезности, характеризующие дискретные решения
счетного
Для введенного в рассмотрение понятия слабого упорядочивания элементов xi ∈X
(решений xi ∈X ) может быть сформулирована следующая теорема.
Теорема 1. Предположим, что отношение является слабым упорядочением на X , т.е.
ассиметрично и отрицательно транзитивно, тогда:
а) для любых пар решений xi , x j ∈X выполняется одно из трех соотношений:
xi x j , x j xi , xi ~ x j ;
б) отношение является транзитивным по полезности ;
в) отношение ~ является эквивалентностью (т.е. рефлексивно, симметрично, транзитивно);
г) ( xi x j и xk ~ x j ) => xi xk
либо
( x
i
x
j
и
x
i
~
x
k
) => x
k
x
j
;
( x
i
~
x
j
и
x
k
x
j
) => x
k
x
i
либо
( xi ~ xk и xk x j ) => xi x j ;
д) отношение (вытекающее из отношений и ~) транзитивно и связно (т.е. с помощью
отношения могут быть связаны любые два решения xi , x j ∈X ).
Так как
предварительно было задано, что
на множестве
решений X
определены
отношения
и ~ (и, соответственно, может быть определено отношение
), т.е.
выполняются
пункты а)-е) сформулированной
теоремы, тогда
отношение
позволяет
формировать слабый порядок (т.е. выполнение пунктов а)-е) свидетельствует об определении
с помощью отношения слабого порядка между решениями xi , x j ∈X ).
В дополнение к свойствам отношения , формирующего слабый порядок на множестве
решений X , рассмотренным (сформулированным) в Теореме 1, могут быть введены в
рассмотрение следующие аксиомы полезности (аксиомы теории полезности решений):
1) если – отношение предпочтения (ассиметричное), ~ – отношение безразличия, то для
любых xi , x j имеет место одно из событий: xi x j , x j xi , xi ~ x j ;
2) xi ~ xi , т.е. исход не отличим от самого себя;
3) xi ~ x j , x j ~ xk => xi ~ xk – транзитивность отношения безразличия (следовательно,
отношение безразличия являются отношением эквивалентности);
U ( x )
20
4) xi x j , x j xk => xi xk ;
5) xi x j , x j ~ xk => xi xk ; xi ~ x j , x j xk => xi xk ;
Если заданные в аксиомах полезности условия выполняются, то в рассмотрение может
быть введена функция полезности, характеризующая предпочтительность решений. В этом
случае для пары альтернатив ( xi ,x j )∈X 2 могут быть определены значения U( xi ) и U ( x j ) ,
которые интерпретируются как значения функции полезности для рассматриваемых
альтернатив и при этом
xi x j
< = >U ( xi ) > U ( x j ) , что также может быть сформулировано
для отношения
в виде:
xi
x j <=> U ( xi ) ≥U ( x j ) .
Так как
выполняются условия, позволяющие интерпретировать
отношение(при
определенном
на множестве X
отношение эквивалентности ~) как
слабый порядок и
определяющие возможность сопоставления решениям xi значений U( xi ) , вытекающие из
бинарных отношений xi с другими решениями x j , тогда должен быть определен способ
формирования значений U( xi ) рассматриваемой дискретной функции полезности .
Таким образом, если на множестве X определены отношения , и ~, само множество
X является счетным и конечным, тогда может быть определена функция U : X → R (функция
полезности, представляющая отношения , и ~) и для пары ( xi ,x j )∈X 2 решений из
множества
X
выражение
x
i
x j
( x
i
x j )выполняются в том случае,
когда
U ( xi ) > U ( x j )
(U ( xi ) ≥U ( x j )) . Для формулировки способа определения значения функции
полезности
U( xi ) для некоторого
xi
предполагаем, что элементы множества X
связаны
отношением нестрогого предпочтения ( ). В этом случае алгоритм формирования значения U(
xi ) предполагает выполнение рассматриваемых ниже шагов.
Пусть значения функции полезности U( xi ) присвоены n альтернативам. Таким образом,
является сформированным множество X n альтернатив (в виде X n = { x1 , x2 ,..., xn } ), для
которых уже определены значения функции полезности U( xi ) . Тогда на текущем шаге
алгоритма рассматривается альтернатива xn+1 , для которой должно быть определено значение
U( x
n+1
)
.
Для альтернативы (решения) xn+1
и множества
X
n
могут быть сформированы
множества
X
+n
и X
n
следующим образом:
X
+n
= { x
i
∈
X
n
|
x
i
x
n+1
}
X n
{ x ∈ X n | x
x }
i
n1
i
Xn
Таким образом, множество
представляет собой решения xi , которые являются не
худшими, чем рассматриваемое решение xn+1 (т.е.
связаны с решением xn+1
следующим
образом:
xi
x
n+1
). Множество X
n
представляет собой решения xi
, для которых решение
x
n+1
является не худшим (предпочтительнее им эквивалентно – в виде
x
n+1
xi ).
∈X n . Т.е.
Через x′обозначим такой элемент множества
X n , что
x
x′для всех
x
i
l
i
l
+
элемент (решение)
x′ представляет собой ―наименьший‖ элемент множества
X n . Через x′
i
i
обозначим такой элемент
множества
X n , что x x
для
всех
x ∈ X n . Таким образом,
i
l
l
элемент (решение)
x′– это "наибольший" элемент множества X n .
i
′
′
является минимальным
Т.е. элемент (решение) xi –
это то решение, у которого U( xi )
среди всех значений U( x )
( при
x
l
∈X n ), решение x′– это то решение, у которого значение
l
+
i
U( x′) является наибольшим среди значений U( x
)
элементов
x
l
множества
X n . Если
i
l
элементов
x
′
и
x′несколько (в каждом из множеств X n , X n ), то выбирается любой из них.
i
i
Выполняется
анализ
сформированных
множеств X
n
и
X
n .
Возможны
следующие
U ( x )
варианты состава этих множеств:
21
1. Xn (тогда Xn );
2. Xn (тогда Xn );
3. Xn , Xn ; Xn Xn ;
4. Xn , Xn ; Xn Xn .
В
случае 1
значение
U( x
n+1
) = U( x
i
′
)+ 1
;
во
втором случае
U ( xn
1 )

U ( xi
)

1
, в
третьем случае
′
′
в
четвертом
случае
принимается, что
U( xn+1 ) = [U( xi ) + U( xi )] / 2 ;
U( x
n+1
)
=
U( x
), где
x
i
- любой (произвольный) элемент множества
X
n

X
n
(элементы
i
множества X
n X
n
имеют одинаковую полезность).
Для реализации приведенного (изложенного) алгоритма должны быть заданы начальные
условия в следующем виде: X 1{x } и U (x ) 0 .
1
1
Реализация приведенного алгоритма позволяет выполнить следующее свойство функции
полезности:
xi
x
j
<=> U( x
i
)
≥
U( x
j
), и в итоге
определить
альтернативу,
для которой
x
*i
= arg max U
(
x
i
)
.
Таким образом,
от предпочтений (отношенийили),
связывающих
1≤i≤N
пары решений ( xi , x j ) , выполняется переход к числовым значениям U( xi ) , U ( x j ) ,
характеризующим рассматриваемые альтернативы, и определение (в завершении)
эффективного решения x*i . Рассматриваемый выше подход предполагает, что возможная
эквивалентность решений xi и x j ( xi ~ x j ) учитываются непосредственно в отношении «не
хуже» ( ) и на основе этого определяется значение функции полезности U( xi ) и U ( x j ) (при
этом U ( xi ) = U ( x j ) ).
Пример.Определение
значений
функции
полезностисиспользованием
(формированием) множеств X
n
и X
n
.
Исходный вид матрицы отношений
( xi
x j ) следующий:
x1
x
2
x
3
x
4
x5
x
6
x
7
x1
0
0
0
0
0
0
0
x2
1
0
1
0
0
0
0
А x3
0
0
0
10
0
1
1
x4
0
1
0
0
1
1
0
x5
0
1
0
0
0
0
0
x6
1
0
0
1
0
0
0
x7
0
0
1
0
0
1
0
Прокомментируем вычисление значений функции полезности U( xi ) по шагам.
1) Решение x1 , U ( x1 ) 0 ;
2) Решение x2 :
X1 ; X1 { x1 } ; U ( x2 ) 1 ;
3) Решение x3 :
X2 { x2 } ; X2 ; U ( x3 ) 0 ;
4) Решение x4 :
X3 { x3 } ; X3 { x2 } ; U ( x4 ) (U ( x3 )U ( x2 )) / 2 1 / 2 ;
5) Решение x5 :
X4 { x4 } ; X4 { x2 } ; U( x5 ) (U( x4 )U( x2 )) / 2 3 / 4 ;
6) Решение x6 :
22
X
5
{ x } ;
X
5
{ x , x } ;
X
5
X
5
{ x } ; U( x ) U( x
4
)1/2
;
4
1 4
4
6
7) Решение x7 :
X
6
{ x } ;
X
6
{ x , x } ;
X
6
X
6
{ x }
; U ( x )

U ( x
3
)0.
3
3 6
3
7
Таким образом, эффективным решение является решение x2 .
Альтернативный подход к определению значений функции полезности U( x ) для
различных решений
xi
∈X
при условии наличия в множестве
X
эквивалентных решений
x j ( xi ~ x j )
связан с определением
классов эквивалентности, множества
классов
эквивалентности и последующего определения значений функции полезности для классов
эквивалентности в их множестве. Определение значений функции полезности для каждого
класса эквивалентности позволяет упорядочить эти классы, выделить среди них эффективные
и, соответственно, определить эффективные решения, принадлежащие этим классам.
Ход изложения метода определения значений функции полезности возможно
прокомментировать с использованием примера. Предположим, что каждому решению xi ∈X
соответствует хотя бы одно (т.е. возможно и более) эквивалентное решение. Тогда должны
быть определены два отношения – отношение строгого предпочтения (его матрицу обозначим
как А1 ) и отношение эквивалентности ~ (его матрицу обозначим как А2 ). Для
вводимого в рассмотрение примера вид
матриц отношений
А1
(для
)
и
А2 (для ~)
следующий:
x1
x2
x3
x4
x5
x6
x7
x1
x2
x3
x4
x5
x6
x7
x1
0
0
0
0
0
0
0
x1
10
10
0
1
0
x2
10
10
0
10
x2
0
10
0
10
0
А x3
0
0
0
0
0
0
0
;
А x3
10
10
0
1
0
.
1
x4
0
10
0
10
0
2
x4
0
0
0
10
0
1
x5
10
10
0
10
x5
0
10
0
10
0
x6
0
0
0
0
0
0
0
x6
10
10
0
1
0
x7
0
10
0
10
0
x7
0
0
0
10
0
1
Эквивалентность решений на множестве X определяет его разбиение на
непересекающиеся непустые классы элементов (непустые непересекающиеся подмножества),
два элемента (или более) принадлежат одному из классов в том случае, когда они
эквивалентны. Формируемые на основе отношения ~ классы элементов (решений xi ∈X )
называются классами эквивалентности.
Через R( xi ) обозначим множество решений, эквивалентных данному решению xi .
Тогда определение R( xi ) будет выполнено следующим образом:
R( xi ) = { x j | x j ∈X и x j R xi } ,
где R - отношение эквивалентности ~.
Для рассматриваемого примера множества X вида: X = { x1 , x2 , x3 , x4 , x5 , x6 , x7 } и
заданных видов матриц А1 и А2 множества эквивалентных элементов имеют вид:
R( x1 ) = { x1 , x3 , x6 } ;
R( x2 ) = { x2 , x5 } ;
R( x3 ) = { x1 , x3 , x6 } ;
R( x4 ) = { x4 , x7 } ;
R( x5 ) = { x2 , x5 } ;
R( x6 ) = { x1 , x3 ,x6 } ;
R( x7 ) = { x4 , x7 } .
23
Видно, что R( xi ) = R( x j ) в том случае, если xi ~ x j . Тогда любые два множества R( xi ) и
R( x j ) либо совпадают, либо не пересекаются. На основе множеств R( xi ) и R( x j )
формируются классы эквивалентности. Реализация рассматриваемого алгоритма предполагает
упорядочивание классов эквивалентности.
Для идентификации различных классов эквивалентности (не пересекающихся классов
эквивалентности) введен в рассмотрение параметр k l , где l - номер класса (в
рассматриваемом случае l 1,3 ). Если отношение R есть отношение эквивалентности,
определенное на множестве X , то множество классов эквивалентности R( xi ) , порождаемых
отношением R обозначено как X /~ (таким образом X /~ – множество классов
эквивалентности множества X ). В результате после выполненных преобразований получим
множество X /~ в виде:
k1 → {
x1
, x3
, x6 };
k2
→ { x2
, x5 };
k3 → {
x4
, x7 } .
Для реализации дальнейших рассуждений в рассмотрение введено отношение
R'
,
обозначенное как ' . Отношение ' определяет строгое предпочтение класса
эквивалентности, обозначенного как k i (множество эквивалентных решений,
соответствующего параметру k i ), над классом эквивалентности, обозначенным как k j (над
множеством эквивалентных решений, соответствующих параметру k j ). Тогда обозначение ki '
k j соответствует строгому предпочтению класса эквивалентности, обозначенного как k i , над
классом эквивалентности, обозначенным как k j .
В соответствии с введенным обозначением отношения строго предпочтения ' для
классов эквивалентности, сформированная выше теорема 1 о свойствах отношения ,
реализующего (при определенном на множестве X отношении эквивалентности ~) слабое
упорядочивание альтернатив xi , может быть дополнена еще одним пунктом.
Теорема 1 (Продолжение). Если отношение является слабым упорядочением на X
(отношение ассиметрично и отрицательно транзитивно), тогда если на множестве X /~
(множестве классов эквивалентности на X в смысле отношения ~) определено отношение ' ,
то:
kh ' k p <=> ∃xi ∈kh и x j ∈k p такие, что xi x j .
В соответствии с введенной в рассмотрение формулировкой Теоремы 1 из отношения
предпочтения для пары решений ( xi , x j ) (т.е. xi x j ) следует строгое предпочтение ' между
классами эквивалентности решений k h и k p (т.е. k h ' k p ), при этом отношение ' является
строгим упорядочиванием. С другой стороны, если реализуется упорядочивание классов
эквивалентности решений, то это обеспечивает и упорядочивание решений в множестве Х.
Таким образом, введение в рассмотрение классов эквивалентности, обозначенных как k l ,
и отношения строгого предпочтения ' для классов эквивалентности позволяет устранить
свойство нестрогого (частичного) упорядочения, вытекающее из отношений (при определении
на множестве X отношения эквивалентности), и перейти к строгому упорядочению классов
эквивалентности, обеспечиваемому отношением ' (т.е. эквивалентность классов не
рассматривается, она исключена). Тогда переход от слабой упорядоченности решений,
обеспечиваемой отношением совместно с отношением ~, к строгому порядку,
обеспечиваемому отношением ' , реализуется путем формирования
классов эквивалентности решений (множества X /~) и исключении отношения ~ при
рассмотрении этих классов (т.е. классы не могут быть эквивалентными).
Свойства введенного в рассмотрение отношения ' :
24
1) асимметрия: если
k
l
' k
h
и
k
h
' k
l
, то найдутся такие
x
, x
j
и
x
′
,x
′
, что
x
i
x
j
и
x
′
x
′
,
i
ij
j
i
при этом
′
′
xi ~ xi и
x j ~ x j ;
2) отрицательная транзитивность: если kl ' k h при xi ∈kl и x j ∈kh , тогда xi x j ; в этом
случае для любого k p ∈X / ~ и любого
xs ∈k
p
следует, что либо xi xs (и в этом случае
kl
' k
p ) либо
xs
x j (в этом случае
k p
' k h ).
Возможность упорядочения классов эквивалентности, идентифицируемых параметрам
k l , путем определения значений функции полезности для каждого класса, обосновывается
следующей теоремой.
Теорема 2. Если отношение на X реализует слабое упорядочивание решений (при
условии наличия для множества Х отношения эквивалентности), а множество X /~ является
счетным, то существует функция U на X такая, что xi
x j <=> U ( xi ) > U ( x j ) для xi , x j ∈X .
В соответствии с формулировками теорем 1 и 2: упорядочивание элементов xi
и
x
j
множества X
вытекает
из упорядочения
классов
эквивалентности,
идентифицируемых
параметром k l ; в случае счетности
множества X /~ каждому классу эквивалентности может
быть поставлено
в соответствие значение функции полезности U (kl
) , которое в дальнейшем
может быть отождествлено со значением функции полезности элементов xi , x j , входящих в
этот класс, т.е.
U ( k
l
) = U ( x
i
) = U ( x
j
)
при
xi , x j
∈R( xi ) либо xi , x j ∈R( x j ) (т.к. классы
эквивалентности R( xi ) и R( x j ) в случае xi ~ x j совпадают (т.е. R( xi
) = R( x j ) при xi ~ x j
)).
Исходя из формулировок теорем 1 и 2 должны быть определены значения функции
полезности для классов эквивалентности множества
X /~ (идентифицируемых параметром
k
l
), т.е. значения
U (k
l
)
.
Затем значение
функции
полезности
класса k l должно быть
сопоставлено функции
полезности
отдельных элементов (решений) xi , образующих
этот
класс эквивалентности.
Таким
образом,
если
xi
∈R( xi ) , то
U( x
i
) = U( kl ) , где
k l –
идентификатор
(индекс,
номер) уникального класса
эквивалентности,
соответствующего
R( x
i
)
. При формировании значений U (k
l
)
в рассматриваемом ниже алгоритме используется
перечисление
множества рациональных
чисел в виде: r1 , r2 , r3 ,... . Напомним, что
рациональными являются числа вида:
1
1
1
1
1
1
1
;
;
;
;
;
;
;...;
1
2
3
4
5
6
7
2
;
2
;
2
;
2
;
2
;
2
;
2
;...;
1
2
3
4
5
6
7
3
;
3
;
3
;
3
;
3
;
3
;
3
;...;
1
2
3
4
5
6
7
Таким образом, в рассмотрение введены значения рациональных чисел, которые в
дальнейшем могут быть использованы при инициализации значений функции полезности
U (kl ) классов эквивалентности k l . Тогда через k1 , k2 , k3 ,... обозначены элементы множества
X /~, через r1 , r2 , r3 ,... – некоторое перечисление множества рациональных чисел (некоторая
упорядоченная цепочка рациональных чисел). В качестве начального условия для реализации
алгоритма определения функции полезности U для элементов X /~ примем, что U( k1 ) = 0 .
Алгоритм формирования значений функции полезности для оставшихся элементов множества
X /~ базируется на анализе свойств отношения ' и имеет следующий порядок шагов:
1) рассматривается некоторый «текущий» класс эквивалентности k m в предположении, что
всем «предшествующим» (m-1)-ому классу эквивалентности присвоены значения U( k1 ),...,U(
km 1 ) .
2) для рассматриваемого km -го класса эквивалентности возможна одна из трех
рассматриваемых ниже ситуаций:
25
а) k
m
' k
h
для всех h m (понятно, что отношение k m ' kh вытекает из отношения
xi x j ,
где xi
∈Rk
m
( x ) , x j ∈Rk ( x ) ), в этом случае U (km ) m ;
h
б) k
h
' k
m
для всех h m (аналогично отношение k h ' km вытекает из отношения x j
xi , где
x j ∈Rkh ( x ) , xi ∈Rkm ( x ) ); в этом случае U (k m )m ;
в) k
h
' k
m
' k
l
для некоторых h и l m , и ни для какого s m
и отличного от
h
и l
не
выполняется
k
h
' k s
' kl , тогда значение
U (km ) принимается
равным
первому
в
перечислении r
1
, r
2
, r
3
,... числу r
k
такому, что U (kh ) rk U (kl ) .
После того,
как значения функции полезности U (kl ) для классов эквивалентности
k l
множества
X /~
сформированы, этими значениями инициализируется функция полезности
U( xi ) решений
xi ∈X , входящих в соответствующие классы: U( xi ) = U( kl ) при xi ∈R( xi ) ,
где
R( x
i
)
–класс эквивалентности, для которого используется идентификатор (индекс, номер
класса k
l
).
В случае,
если для решений xi ∈X вычислены значения функции полезности
U( x ) , определяется эффективное решение в соответствии с условием
x*
= arg max U (x
)
.
i
i
1≤i≤N
i
3. Программа выполнения работы
Для
варианта
задания,
связанного с
использованием
множеств
X
n
и
Xn ,
предусматривается следующий порядок действий по выполнению лабораторной работы:
1) реализовать объявление и инициализацию матрицы отношений между решениями в
соответствии с вариантом задания;
2) реализовать процедуру определения для каждого рассматриваемого решения
xn+1
соответствующих ему множеств
X
+n
и X
n
, которые определяют для решения
x
n+1
не худшие
по отношению к нему решения
(множество
X
+n
) и не лучшие по отношению к нему решения
(множество X
n
); при определении множества
X
+n
необходимо выполнять просмотр (n+1)-го
столбца матрицы отношений, при определении множества
X
n
необходимо
выполнять
просмотр (n+1)-ой строки
матрицы
отношений, для
рассматриваемого
элемента
x
n+1
выполнить вывод множеств
X
+n
, X
n
;
3) реализовать
процедуру выполнения
условий
X
n

( X
n ), X
n ( X
n ),
X
n

X
n

,
X
n

X
n

; тем самым определяется способ вычисления значений функции
полезности для решения xn+1 ; реализовать вывод информации о выполняющемся условии;
4) реализовать процедуру вычисления значения функции полезности для текущего
рассматриваемого решения xn+1 ;
5) реализовать процедуру управления процессом вычисления значений функции полезности
для каждого элемента множества Х (решения множества Х); реализовать в рассматриваемой
процедуре определение максимального значения функции полезности и соответствующего
ему решения; выполнить вывод всех решений xi ∈X и соответствующих им значений функции
полезности.
Для варианта задания, связанного с использованием классов эквивалентности,
предусматривается следующий порядок действий по выполнению лабораторной работы:
1) реализовать инициализацию матриц отношений строго предпочтения А1 и эквивалентности
А2;
2) реализовать процедуру, формирующую на основе матрицы отношения эквивалентности А2
классы эквивалентности R( xi ) ( xi ∈X );
26
3) реализовать процедуру, выполняющую сравнение полученных классов эквивалентности
R( xi ) ( xi ∈X ), исключение повторяющихся классов, формирующую множество X /~
уникальных классов эквивалентности решений k l ;
4) реализовать процедуру, выполняющую упорядочивание классов эквивалентности k l с
определение соответствующих им значений функции полезности U( kl ) ;
5) реализовать процедуру, которая выполняет инициализацию значений функции полезности
элементов (решений) U( xi ) множества Х, входящих в соответствующие классы
эквивалентности k l , значениями функции полезности этих классов U( kl ) ; разрабатываемая
процедура также выполняет упорядочивание решений xi ∈X с точки зрения значений их
функции полезности и определяет решение xi* ∈X , для которого значение функции
полезности является максимальным;
6) реализовать вывод исходных данных, промежуточных и конечных результатов: матриц
отношений А1 и А2, классов эквивалентности R( xi ) ( xi ∈X ), множества X /~ не
повторяющихся ("уникальных") классов эквивалентности, полученных значений функции
полезности U( kl ) для каждого класса k l , значений функции полезности для решений xi ∈X ,
соответствующих этим классам, эффективных решений с максимальным значением функции
полезности.
4.Задание на работу
Вариант 1. Используя метод, реализующий формирование множеств
X
n и
X
n , а также
их последующий анализ (с
точки зрения Xn ( Xn ),
X
n

(
X
n

),
X
n

X
n

,
X
n

X
n

)
, выполнить для заданного вида матрицы отношения
предпочтения А1
определение значений функции полезности U( xi ) решений и определение
по формируемым значениям функции полезности эффективных решений
xi* ∈X . Матрица
отношения предпочтения имеет следующий вид:
x1
x2
А1 x3
x4
x5
x6
x7
x
1
x
2
x
3
x4
x
5
x
6
x
7
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
1
0
0
1
0
1
0
0
1
1
0
0
1
0
0
0
0
0
1
0
0
1
0
0
0
0
0
1
0
0
1
0
Вариант 2. Используя метод, реализующий формирование классов эквивалентности R( xi
) ( xi ∈X ), формирование множества X /~ неповторяющихся классов эквивалентности k l ,
выполнить разработку программы, определяющей значения функции полезности U (kl ) для
этих классов и значения функции U( xi ) для решений xi ∈X , с последующим определением
эффективных решений, для которых x*i = arg max U (xi ). Вид матриц отношений
предпочтения и эквивалентности следующий:
1≤i≤N
27
x1
x2
x3
x4
x5
x6
x7
x1
x2
x3
x4
x5
x6
x7
x1
0
0
0
0
0
0
0
x1
10
10
0
10
x2
10
10
0
10
x2
0
10
0
10
0
А1
x3
0
0
0
0
0
0
0
;
А
x
3
10
10
0
10
x4
0
10
0
10
0
2
x4
0
0
0
10
0
1
x5
10
10
0
10
x5
0
10
0
10
0
x6
0
0
0
0
0
0
0
x6
10
10
0
10
x7
0
10
0
10
0
x7
0
0
0
10
0
1
.
Вариант 3. Задана матрица отношения нестрогого предпочтения. Используя метод,
реализующий формирование классов эквивалентности R( xi )
( xi ∈X ), формирование
множества X /~ неповторяющихся классов эквивалентности k l ,
выполнить разработку
программы, определяющей значения функции полезности U (kl ) для этих классов и значения
функции U( xi ) для решений xi ∈X , с последующим определением эффективных решений,
для которых x*i = arg max U (xi ). Вид матрицы следующий:
1≤i≤N
A
x
1
x
2
x
3
x
4
x
5
x
6
x
7
x
8
x
9
x
10
x
1
0
0
0
1
0
0
0
1
0
0
x
2
0
0
1
0
1
0
0
0
1
0
x
3
1
0
0
1
0
1
1
1
0
1
x
4
1
1
0
0
1
0
0
1
1
0
x
5
0
1
0
0
0
0
0
0
1
0
x
6
1
0
1
0
0
0
1
0
0
1
x
7
1
0
1
0
0
1
0
1
0
1
x
8
1
1
0
1
1
0
0
0
1
0
x9
0
1
0
0
1
0
0
0
0
0
x
10
1
0
1
0
0
1
1
0
0
0
5. Контрольные вопросы
5.1. Чем вызвана необходимость использования аппарата функции полезности?
5.2. В чем состоят условия существования функции полезности, определяемой на множестве
решений?
5.3. Какова связь между бинарным отношением для пары решений и значениями их функции
полезности?
5.4. В чем заключается слабый порядок на множестве решений Х?
5.5. В чем заключается строгий порядок на множестве решений Х?
5.6. В чем состоят аксиомы теории полезности и каков их смысл?
5.7. Каков алгоритм процедуры определения значений функции полезности с использованием
множеств доминируемых и доминирующих решений?
5.8. Какие особенности задания отношений на множестве решений Х позволяет учесть
введение классов эквивалентности (какой вид отношения на множестве Х позволяет
исключить введение классов эквивалентности)?
5.9. Каким образом реализуется связывание классов эквивалентности с использованием
отношения предпочтения для классов?
5.10. Какое условие должно быть выполнено для существования функции полезности на
множестве классов эквивалентности?
5.11. В чем заключается алгоритм определения значений функции полезности для классов
эквивалентности?
5.12. Каким образом определяются значения функции полезности для решений, если значения
функции полезности для классов эквивалентности известны?
28
ЛАБОРАТОРНАЯ РАБОТА №3
ИССЛЕДОВАНИЕ ПРИМЕНЕНИЕ АППАРАТА МНОГОМЕРНОЙ ПОЛЕЗНОСТИ
ДЛЯ ПРИНЯТИЯ РЕШЕНИЙ
1. Цель работы: исследовать применение аппарата теории многомерной полезности при
принятии решений по выбору эффективных альтернатив.
2. Теоретическое введение
При реализации принятия решений в случае многих критериев (свойств, характеристик)
используется многомерная функция полезности, т.е. функция полезности, учитывающая для
каждого решения его полезности по каждому критерию. Подход, определяющий
использование многомерной полезности, рассмотрим на примере двух критериев (свойств,
характеристик решений). Обозначим через K1 и K 2 множества возможных значений каждого
из критериев, k1i , k 2i - соответственно значения каждого из критериев для некоторого решения xi
(т.е. k1i K1 ; k 2i K 2 , i1, n ). Понятно, что множества значений K1 и K 2 соответствующих
критериев являются счетными и конечными. Если через xi обозначено некоторое i -е решение ( xi
∈X ), тогда это решение характеризуется парой значений ( k1i , k 2i ). В соответствии с
постановкой задачи необходимо определить то решение x*i , которое будет являться
эффективным с точки зрения его общей полезности.
Основное понятие многокритериальной теории полезности (теории многомерной
полезности) – это понятие замещения по полезности или просто замещения. Понятие
замещения по полезности (в дальнейшем замещения) связано с предположением о том, что
приращение по одному критерию (k 2 ) может быть скомпенсировано путем уступки по
другому критерию (k1 ) . Для увеличения оценки полезности по второму критерию наk 2
требуется выполнить уступку по первому критерию -k1 (т.е. для первого критерия найдется
такая уступка -k1 , которая обеспечит увеличение второго критерия наk 2 ). Если xi и x j -
некоторые решения, тогда ( k1i , k 2i ) – значения критериев, соответствующие решению xi , а (
k1ik1 , k 2ik 2 ) (или же ( k1j , k 2j )) – значения критериев, соответствующие решению x j .
Если существует возможность уступки по первому критерию (уступки - Δk1 ) для
решения xi с целью получения нового решения x j с увеличением для него наk 2 значения
критерия K 2 , тогда решение xi эквивалентно решению x j с точки зрения общей полезности
(полезность решения xi равна полезности решения
x j , решение
xi
эквивалентно решению
x j ,
xi ~ x j ).Данный
фактможет
быть
обозначен
следующим
образом:
(k
1i
, k
i2
) ~ (k
1i
k
1
, k
2i
k
2
) ,
либо если k1j
k
1i

k
1
, k
2j

k
2i

k
2
, то
(k
1i
, k
2i
)
~
(k
1j
, k
2j
)
.
Аналогичным образом может быть выполнен переход из точки x j
с координатами (k
1j
, k
2j
)
в
точку xl с координатами
(k
1l

k
1j

k
1'
, k
1l
k
2j

k
2'
)
, где
k
1'
и
k
2'
-
уступки
и
приращение, соответствующие переходу отрешения
x j к решению
xl . При этом x j ~ xl
и
(k1j , k2j ) ~ (k1l , k 2l ) . Тогда могут быть сформированы все возможные замещения для каждого
решения xi (полученные точки x j , xl и т.д.) т.е. получено множество точек критериального
пространства K1 K 2 , которые эквивалентны решению xi с точки зрения общей полезности
(полезности по двум критериям). Точки такого (одного) множества образуют одну кривую,
называемую кривой безразличия. Точки, лежащие на разных кривых безразличия, имею
разную полезность (обладают разной полезностью).
29
Понятия замещения для решений xi и x j , а также кривых безразличия
прокомментированы на Рис.1.
a) б)
Рисунок 1 – Замещение по полезности и кривые безразличия для двух критериев
а) замещение по полезности; б) кривые безразличия для двух критериев
Обозначив U (k1 , k2 )
общую полезность решений (x
i
, x
j
, x
l
,...
)
(многомерную функцию
полезности)
имеем,
что
U
1
(k
1
, k
2
)

const
,
U
2
(k
1
, k
2
)

const
,
U
3
(k
1
, k
2
)

const
,
т.е.
полезность
решений
при
переходе по кривой
безразличия
U
h
( k
1
,k
2
) = const
не
( h = 1,3 )
изменяется. Решения
x
i
,
x
j
,
x
l
, которым соответствуют ( k i
,k
i
)
,
( k
j
,k
j
)
,
( k
l
,k
l
)
являющиеся
1
2
1
2
1
2
эквивалентными, лежат на одной кривой безразличия.
Кривые безразличия – это линии одинаковых значений двумерной функции полезности
U (k1 , k2 ) , согласованных с предпочтениями ЛПР (с предпочтениями ЛПР согласуются
значения двумерной функции полезности U (k1 , k2 ) ). Под согласованностью следует
понимать выполнение следующих условий, связанных с кривыми безразличия:
( xi x j ) <=> ( k1i ,k2i ) ( k1j ,k2j ) <=> U( k1i ,k2i ) ≥U( k1j ,k2j ) ,
где U (k1i , k2i ) и U (k1j , k 2j ) - разные кривые безразличия, соответствующие решениям xi и x j
, лежащим на них.
Т.к. понятие замещения связано с приращением одного критерия за счет уступок по
другому критерию, то в рассмотрение должен быть введен коэффициент замещения,
обозначенный через
. Если в точке (k1i , k 2i ) за единиц критерия K 2 можно уступить

единиц критерия K1 , тогда предельный коэффициент замещения в точке (k1i , k 2i ) равен
(Рис. 1а)). Тогда при наличии кривых безразличия могут быть вычислены локальные
коэффициенты замещения
в каждой точке. Понятно, что коэффициент
в общем виде не
является постоянным, а зависит от вида кривой безразличия и выбора точки (k1i , k 2i ) на этой
кривой. Т.е. при использовании даже одной кривой безразличия и разных точек на ней могут
быть получены разные коэффициенты
.
Для формирования вида многомерной (двумерной) функции полезности U (k1 , k 2 )
необходимо выполнить априорное задание свойств предпочтений (условий, которым должны
удовлетворять предпочтения), которые приводят к удобным видам функции полезности.
Таким образом, должно быть определено условие, обеспечивающее существование простых (в
частном случае, аддитивных) функций полезности , т.е. предпочтения по каждому из
критериев (предпочтения по группе критериев) должны быть такими, чтобы обеспечивать
существование аддитивной функции полезности. В общем виде аддитивная функция
полезности имеет форму:
n
U (k1 , k 2 ,..., k h )U j (k j ) ,
j1
U ( x )
30
где
U j – j-я функция полезности для j-го критерия. В частном случае двух критериев K1 и
K
2
аддитивная функция полезности имеет вид: U (k1 , k2 ) U1 (k1 ) U 2 (k2 ) .
Условием, определяющим существование аддитивной (в частном случае, двумерной)
функции полезности является условие соответственных замещений. Условие соответственных
замещений может быть прокомментировано следующим образом на основе Рис. 2. Для
формулировки условия рассматриваются четыре точки (решения): x1 с координатами (k11 , k 21 ) ,
x
2 с координатами (k11 , k22 ) , x3 с координатами (k12 , k21 ) и x4 с координатами (k12 , k22 ) . В
точке x1 (k11 , k 21 ) за увеличение K 2 на b единиц необходимо заплатить (уступка) a единиц, в
точке
x
2
(k
11
, k
22
) за увеличение
K 2 на c единиц необходимо заплатить
a
единиц,
в точке
x
3
(k
12
, k
21
) за увеличение
K
2
на b единиц необходимо заплатить d
единиц.
Сколько
необходимо заплатить в точке
x
4
(k
12
, k
22
) , чтобы получить увеличение
K
2
на c единиц.
Рисунок 2 – Изменение значений критериев для условия соответственных замещений
Условие соответственных замещений предполагает, что если при заданных условиях для
точек x1 , x2 , x3 , значениях a, b, c, d получим, что для приращения в точке x4 дополнительно
по критерию K 2 c единиц необходимо заплатить (уступка) d единиц по критерию K1 , то условие
замещения выполняется. Таким образом, условие соответственных замещений выполняются, если
для точки (решения) x4 при увеличении K 2 на c единиц необходимо заплатить (уступка) d единиц
по K1 . Выполнение условия соответственных замещений гарантирует аддитивный вид функции
полезности:U (k1 , k2 ) U1 (k1 ) U 2 (k2 ) . Существование аддитивной функции полезности U (k1 ,
k2 ) обосновывается в соответствующей теореме
Льюиса-Тьюки (формулируемой ниже), в доказательстве которой сформулирован способ
(алгоритм) построения изолиний функции полезности (линий одинаковых значений функции
полезности), определения на их основе вида функций U1 (k1 ) и U 2 (k 2 ) . При этом данный
алгоритм обеспечивает выполнение условия соответственных замещений для формируемых
изолиний аддитивной функции полезности U (k1 , k2 )
и вида функций U1 (k1 )
и
U
2
(
k
2
)
. Т.е.
реализация алгоритма обеспечивает определение
U
1
(
k
1
)
,
U
2
(
k
2
)
, изолиний
U (k1 , k2 ) при
выполнении условия соответственных замещений.
Теорема о существовании аддитивной функции полезности (Льюиса-Тьюки).
Структура
предпочтений
аддитивна,
т.е.
аддитивная
функция
полезности
U
(
k
1
,
k
2
)

U
1
(
k
1
)

U
2
(
k
2
)
существует тогда,
когда
выполняется
условие соответственных
замещений.
Доказательство. Доказательство необходимости выполним на основе Рис.2. Т.к. точки
(k11 , k 21 )
и
(
k
11

a
,
k
21

b
)
лежит на одной кривой безразличия (изолинии функции
полезности),
то для них выполняется условие (с учетом предположения об аддитивности
U (k1 , k2 ) ):
31
U1 (k11 ) U 2 (k 21 ) U1 (k11 a) U 2 (k 21 b) .
Аналогичные условия выполняются для точек x2 ( k11 ,k22 ) и x3 ( k12 ,k21 ) :
U (k 1 ) U (k 2 ) U (k 1 a) U (k 2 b) ;
1 1 2 2 1 1 2 2
Складывая второе и третье равенства и вычитая из полученной суммы первое, получим,
что для точки x4 ( k12 ,k22 ) выполняются:
U1 (k12 ) U 2 (k 22 ) U1 (k12 d ) U 2 (k 22 c)
т.е. условие соответственных замещений выполняется.
Доказательство достаточности выполним с точки зрения обоснования способа
определения функций U1 (k1 ) и U 2 (k 2 ) в предположении, что условие соответственных
замещений выполняется. Т.е. при обосновании процедуры, которая носит название процедуры
совместного шкалирования (процедуры определения U1 (k1 ) и U 2 (k 2 ) ), проконтролируем
выполнение условия соответственных замещений. Доказательство достаточности и
обоснование процедуры определения функций U1 (k1 ) и U 2 (k 2 ) выполним с использованием
Рис. 3.
Рисунок 3 – Реализация совместного шкалирования при аддитивной структуре
предпочтений.
I– первая кривая безразличия;
II– вторая кривая безразличия;
III– третья кривая безразличия.
Алгоритм формирования значений U1 (k1 ) и U 2 (k 2 ) имеет следующие шаги:
1) пусть k10 и k 20 - наименьшие значения оценок соответствующих критериев K1 и K 2 ; для
координат k10 , k 20 (решения с координатами (k10 , k 20 ) ) предполагается, что
U (k10 , k20 ) U1 (k10 ) U 2 (k20 ) 0 ;
2) для значения k11 параметра k1 (k11 k10 ) задается, что U (k11 )1 ; это будет первая кривая
безразличия, которая характеризуется значением U (k1 , k2 )1; при этом k2 0 ; т.е. U (k11 , k20
)1 (при k20 0 )
3) определим такое значение второго критерия K 2 , что (k11 , k20 ) ~ (k10 , k21 ) (т.е. решение с
координатами
(k
0
, k
1
)
лежит
на одной кривой безразличия с решением
(k
1
, k
0
)
), тогда
1
2
1
2
U
2
(k
21
)

1
; т.к. коэффициенты k
11
, k
21
известны, то они соответствуют решению
x2 , которое
не находится
(не
лежит) на
кривой безразличия c U (k1 , k2 )1(т.е.
x
2
( k
11
,k
21
)
не
принадлежит кривой безразличия c U 2 (k11 ) 1 и U 2 (k 21 )1);
32
4) т.к. решение
x
2
( k
11
,k
21
)
является известным, тогда определяются решения
x
3
( k
12
,k
20
)
и
x
4
( k
10
,k
22
)
,
которые лежат на одной кривой безразличия с x2 ;
таким образом для решений
x2 , x3 , x4
выполняется условие x2 ~ x3 ~ x4 (или
(k
11
, k
21
)
~ (k
12
, k
20
) ~ (k
10
, k
22
) ); при этом
значение
U (k1 , k 2 )
и
U1 (k1 ) ,
U
2
(k
2
)
задается
следующим
образом:
U ( k11 ,k21 ) = U ( k12 ,k20 ) = U ( k10 ,k22 ) = 2 ;
U 1 ( k12 ) = 2 ;U 2 ( k22 ) = 2 ;
5) реализация предшествующих шагов процедуры позволяет определить, что в соответствии с
условием соответственных замещений k21 k11 d , тогда решения x5 и x6 являются
одинаковыми (эквивалентными) по предпочтительности (т.е. x5 ~ x6 ) и принадлежит одной
кривой безразличия;
6) т.к. значения критериев K1 и K 2 для решений x5 и x6 определены, должны быть
идентифицировать значения k13 и k 23 такие, что для них выполняется условие:
(k13 , k20 ) ~ (k12 , k21 ) ~ (k11 , k22 ) ~ (k10 , k23 ) ,
т.е. выбираются такие значения k13 , k 23 , для которых и формулируется приведенное условие;
для решений с координатами (k13 , k20 ) , (k12 , k21 ) , (k11 , k22 ) , (k10 , k23 ) задается значение
функции полезности U (k1 , k 2 ) 3 ; откуда значения одномерных функций полезности
определяются следующим образом U1 (k13 ) 3 ;U 2 (k23 ) 3 ; итоги реализации данного шага
является определение координат (k11 , k 23 ) , (k12 , k22 ) , (k13 , k21 ) тех решений, которые лежат
на следующей кривой безразличия c U (k1 , k 2 ) 4 ; при этом для решений с
рассматриваемыми значениями критериев K1 и K 2 выполняется условиие эквивалентности
(вытекающее из условия соответственных замещений) (k11 , k 23 ) ~ (k12 , k22 ) ~ (k13 , k21 ) ;
7) продолжая действия подобным образом,
должны быть получены значения k
1j
и k
2j
( j
) , которые входят в пары
(k
j
, k
0
)
,
( k
0
,k
j
4, n
) ; эти значения (при условии присвоения
1
2
1
2
соответствующих решениям значений U (k1 , k 2 ) ) используются при определении значений
одномерных функций полезности U1 (k1j ) , U 2 (k 2j ) ( j 4, n) .
Итогом рассмотренной процедуры являются дискретные значения одномерных дискретных
функций полезности решений по каждому критерию U1 (k1h ) , U 2 (k 2h ) где h 1, n .
После формирования вида функций U1 (k1 ) и U 2 (k 2 ) с использованием введенного в
рассмотрение метода необходимого выполнить агрегирование этих функций для получения
многомерной (двумерной) функции полезности U (k1 , k 2 ) . Агрегирование функций U1 (k1 ) и
U
2
(k
2
)
(получение обобщенной многомерной функции полезности U (k1 , k 2 ) ) используется
выражение U (k
1
, k
2
) jU
1
(k
1
) (1 j)U
2
(k
2
) , где
j -
коэффициент шкалирования.
Для
определения шкалирующего коэффициента необходимо:
1) на
основе заключений ЛПР
определить
два
эквивалентных
решения x i и x j
(т.е.
(k
1i
, k
2i
)
~ (k
1j
, k
2j
) ), лежащие на одной кривой безразличия;
2)
вычислить
значение
j
путем
решения
уравнения
вида
jU 1 (k1i ) (1 j)U 2 (k2i ) jU 1 (k1j ) (1 j)U 2 (k2j ) .
Пример реализации принятия решения на основе аппарата теории многомерной
полезности.
Рассматривается задача покупки автомобиля. Параметрами, характеризующими решение
(модель автомобиля), являются цены и пробег. Т.к. известно, что по мере роста цены на
некоторый предмет (объект, приобретение и т.д.) полезность этого предмета (и в конечном
итоге решения) стремится к 0. Т.е. при достаточно большой цене предмет (решение)
33
становятся бесполезным. Наоборот, при небольшой цене полезность предмета (решения)
является более значительной. Поэтому с точки зрения параметра «цена» полезность решения
будет минимальный при большом значении этого параметра и максимальный при малом
значении параметра. Поэтому в качестве критерия K1 (свойства, характеристики решения)
следует рассматривать критерий вида K11/ цена . Аналогичные рассмотрения могут быть
выполнены с точки зрения параметра «пробег». Если пробег минимальный, то полезность
решения будет являться значительной, если пробег значительный, то полезность решения
наоборот будет являться минимальной. Поэтому в качестве второго критерия K 2 следует
рассматривать критерий вида K 21/ пробег .
Диапазон значений для первого параметра решения (цена), на основании которого
определяется критерий K1 , заданы равным [ 5 тыс;50тыс ] или в единицах тысяч - [ 5;50 ] . Для
определения многомерной функции полезности U (k1 , k 2 ) и одномерных функций U 1 (k1 ) , U
2 (k 2 ) на интервале [ 5;50 ] определим следующие значения (дискретные значения), для
некоторых значения функций будут вычисляться: 5, 10, 20, 50. Соответственно при переходе к
критерию (K11/ цена) его значения будут определены на интервале [ 0.02;0.2 ] , а значения K1
, которые будут рассматриваться следующие: 0.02; 0.05; 0.1; 0.2.
Аналогичным образом строятся рассуждения относительно критерия K 2 . Диапазон
значений параметра «пробег», на основании которых определяются значения критерия K 2 ,
задан в виде [ 10;100 ] (измеряется в тысячах километров). Дискретные значения, для которых
определяются значения функций U (k1 , k 2 ) , U 1 (k1 ) , U 2 (k 2 ) заданы следующими:
10,40,70,100. Тогда при переходе к критерию K 21 / пробег диапазон значений получен в виде
[ 0.01;0.1 ] , а дискретные значения критерия следующие: 0,01; 0,0143; 0,025; 0,1.
В
результате для диапазонов [ 0.02;0.2 ] ,[ 0.01;0.1 ]
(значений 0,02; 0,05; 0,1; 0,2 и 0,01;
0,0143;
0,025; 0,1) сформирована
двумерная функция полезности
(в соответствии с
приведенным алгоритмом) U (k
1
, k
2
)
и одномерные функции полезности
U
1
(
k
1
)
и
U
2
(
k
2
)
.
При переходе от значений критериев K11/ цена и
K 21/ пробег к указанным выше
значениям параметров «цена» и «пробег» одномерные функции полезности каждого из
параметров получены в виде, представленном на Рис.4.
а)
б)
Рисунок 4 – Виды сформированных функций полезности U1 и U 2
а) функция полезности для параметра «цена»;
б) функция полезности для параметра «пробег»;
34
Так как дискретные значения функций U 1 (k1 ) и U 2 (k 2 ) получены, тогда должны быть
определены аналитические формы этих функций (для постановки в них произвольных
значений рассматриваемых параметров, характеризующих решения). Т.к. в большинстве
случаев функции являются нелинейными, то для них может быть задана следующая
аналитическая
форма:
U
1
= a
k
1
+ b ( k
1
)
2
;U
2
= a
2
k
2
+ b ( k
2
)
2
.
Для
определения
1
1
2
коэффициентов
a
i
, b
i
(i

1,2)
в приведенных аналитических
функциях
U1,U2
применимы
методы аппроксимации (данный этап в рамках лабораторной работы необходимо выполнить
самостоятельно).
Т.к. вид двумерной
функции полезности U (k
1
, k
2
)

jU
1
(k
1
)

(1

j)U
2
(k
2
) ,
тогда
должен быть определен
коэффициент масштабирования j . Для этого должны
быть
определены два решения, являющиеся эквивалентными (лежащими на одной кривой
безразличия), т.е. (k
1i
, k
2i
)
~
(k
1j
, k
2j
)
. Допустим, что равноценными являются решения с
k
1i
=10,
k
2i
= 90 и k1j = 40 , k2j = 10 (пробег – 90 тыс. км, цена – 10 тыс. у.е.; пробег – 10 тыс. км, цена –
40
тыс. у.е.). Тогда
получим jU 1 (10) (1 j)U 2 (90) jU 1 (40) (1 j)U 2 (10) . В
итоге
значение j 0.59 .
Т.к. аналитические формы выражений для U 1 (k1 ) и
U 2 (k 2 ) получены, значение j
вычислено, тогда могут быть определены значения U (k
1
, k
2
)
при любых значениях входных
параметров k1
и k 2 . Результаты сравнения четырех вариантов решений сведены в Таблицу 1.
Таблица 1. Двумерная функция полезности в задаче выбора решения.
Вариант
Цена
Пробег
U 1 (k1 )
U 2 (k2 )
U (k1 , k 2 )
1
40
10
0,5
3
1,525
2
10
80
2
0,8
1,508
3
18
40
1,5
2
1,708
4
25
60
1,3
1,3
1,3
В результате эффективным решением является третье, у которого обобщенная функция
полезности U имеет максимальное значение.
3. Программа выполнения работы
Выполнение задания предусматривает реализацию следующего порядка действий по
выполнению лабораторной работы:
1. Для введенных диапазонов изменения параметров решений (критериев решений) и
соответствующих значений этих критериев реализовать процедуру построения двумерной
функции полезности U ( k1 ,k2 ) , в которой выполнить определение дискретных значений
одномерных функций полезности U1 ( k1 ) и U2 ( k2 ) для соответствующих критериев
(реализовать процедуру формирования значений U1 ( k1 ) и U2 ( k2 ) ).
2. Выполнить построение линий безразличия для двумерной функции полезности U ( k1 ,k2 ) ,
которые в дальнейшем будут использоваться для определения эквивалентных решений,
лежащих на одной из этих линий. Координаты этих решений будут использованы при
вычислении коэффициента масштабирования j.
3. Реализовать процедуру аппроксимации полученных дискретных значений одномерных
функций
полезности
U1 ( k1 ) и
U2 ( k2 ) с использованием
полиномов второй
степени
U
1
= a
k
1
+ b ( k
1
)
2
;U
2
= a
2
k
2
+ b ( k
2
)2
, результатом реализации
этой процедуры
являются
1
1
2
коэффициенты этих аналитических кривых a1 , b1 , a2 , b2 .
35
4. Выполнить формирование процедуры вычисления значения коэффициента
масштабирования j, при реализации которой используются координаты ( k i
,k
i
)
и
( k
j
,k
j
)
1
2
1
2
соответствующих
эквивалентных решений xi и x j , лежащих на одной кривой безразличия
(т.е. в качестве исходных данных для этой процедуры использованы координаты
( k i
,k i
) и
1
2
( k
1j
,k
2j
)
решений
xi и x j , выбранных на одной кривой безразличия, сформированной в
пункте 2).
5. Для задаваемых в варианте характеристик решений с использованием определенных ранее
(процедурой в пункте 3) аналитических функций U1 a1k1b1( k1 )2 ;U2 a2k2b2( k2 )2
реализовать процедуру вычисления значений одномерных функций полезности U1 ( k1 ) и
U2 ( k2 ) , а затем двумерной функции полезности U ( k1 ,k2 ) с учетом коэффициента
масштабирования j. В разрабатываемой процедуре выполнить определение эффективного
решения с максимальным значением двумерной функции полезности (передаваемыми в
реализуемую процедуру наряду с исходными данными являются параметры a1 , b1 , a2 , b2 ).
6. Выполнить вывод: а) линий безразличия, б) полученных значений одномерных функций
полезности
U
1
( k
1
)
и
U
2
( k
2
) , в) видов аппроксимирующих функций
U
1
a k
b ( k
)
2
;
1
1
1
1
U
2
a k
2
b ( k
2
)2 ,
г)
значений одномерных и двумерной функций
полезности
для
2
2
решений,
указанных
в
варианте задания, д) эффективных решений
x*i
с максимальным
значением двумерной функции полезности U ( k1 ,k2 ) .
4.Задание на работу
Вариант 1. Задача состоит в выборе одной из альтернатив, представляющих собой
выставленные на продажу автомобили. Критериями (характеристиками) решений являются:
K
1 1 / цена и K 21 / пробег . Используя метод, реализующий построение и исследование
двумерной функции полезности, для заданных диапазонов значений критериев и их
(критериев) дискретных оценок выполнить: формирование линий безразличия U( k1 ,k2 ) ,
определение на их основе дискретных значений оценок одномерных функций полезности для
каждого из критериев k1 и k2 , аппроксимацию дискретных значений одномерных функций
полезности с использованием полиномов второй степени, вычисление коэффициента
масштабирования j на основе выбираемых ЛПР по кривым безразличия решениям. С
использованием сформированных промежуточных решений выполнить для задаваемых
характеристик альтернатив вычисление значений одномерных функций полезности,
двумерной функции полезности и реализовать выбор эффективного решения. Выполнить
вывод исходных данных, всех промежуточных и конечных результатов. Исходными данными
для решаемой задачи являются: параметр "цена" изменяется в диапазоне , параметр
"пробег" в диапазоне [20,80] . Шаг дискретизации первого параметра задан равным 25, шаг
дискретизации второго параметра задан равным 20. Соответственно, для первого критерия
диапазон изменения ег о значений задан в виде , для второго кр итерия диапа зон
задан в виде [0,0125;0,05] . Выбор двух эквивалентных решений на одной из кривых
безразличия, сформированных программно, выполнить самостоятельно. Данные, на основании
которых выбирается эффективное решение, имеют следующие значения:
Вариант
Цена
Пробег
1
30
45
2
50
30
3
80
20
4
25
55
[0,001; 0,04 ]
[ 25, 100 ]
36
Вариант 2. Перед выпускником учебного заведения стоит проблема выбора
оптимального места дальнейшей работы. Выбор определяется значениями критериев:
К
1 - величина зарплаты;
К
2 - процент творческой работы;
К
3 - время, за которое можно добраться до работы.
Диапазон значений для первого параметра решения (зарплата), на основании которого
определяется критерий К1 , заданы равным [50 тыс; 200 тыс] или в единицах тысяч – [50,200].
Для определения многомерной
функции полезности U ( k1 ,k2 ,k3 ) и одномерной функции
U1( k1 ) на интервале [50,200]
заданы следующие значения (дискретные значения), для
некоторых значения функций будут вычисляться: 50, 75, 100, 125, 150, 175, 200.
Диапазон значений параметра «процент творческой работы», на основании которых
определяются значения критерия К2 , задан в виде [20;60]. Дискретные значения, для которых
определяются значения функции U ( k1 ,k2 ,k3 ) и одномерная функция U 2 ( k2 ) заданы
следующими: 20,30, 40, 50, 60.
Диапазон значений параметра «время, за которое можно добраться до работы», на
основании которых определяются значения критерия К3 , задан в виде [20;70]. Дискретные
значения, для которых определяются значения функций U ( k1 ,k2 ,k3 ) и одномерная функция
U3( k3 ) заданы следующими: 20,30, 40, 50, 60, 70.
Для сформированных диапазонов значений критериев необходимо определить
дискретные значения одномерных функций полезности U1( k1 ) , U 2 ( k2 ), U3( k3 )
На основании полученных значений одномерных функций полезности U1( k1 ) ,U 2 ( k2 ),
U3( k3 ) должны быть определены аналитические формы этих функций (для постановки в них
произвольных значений рассматриваемых параметров, характеризующих решения). Для них
должны
быть
заданы
следующие
аналитическиеформы:
U
( k
) a k
1
b ( k
1
)2
,
1
1
1
1
U
( k
2
) a k
2
b ( k
2
)2 , U ( k
) = a k + b ( k )
2
. Для определения
коэффициентов
в
2
2
2
3
3
3
3
3
3
приведенных аналитических функциях U1( k1 ) , U 2 ( k2 ), U3( k3 ) необходимо применить метод
наименьших квадратов
Т.к.
аналитические формы выражений для U1( k1 ) и U 2 ( k2 ) получены, а многомерная
полезность
U ( k
1
,k
2
,k
3
)
является аддитивной
функцией, тогда
для заданных в таблице
значений параметров определить эффективное решение.
Предприятие
Критерии
k
1
k2
k3
x
1
100
50
30
x
2
140
30
50
x
3
170
25
45
x
4
130
15
10
x
5
140
40
40
37
Вариант 3. Перед ЛПР стоит проблема выбора объекта недвижимости, в который он
может вложить средства (покупка дачи). Выбор определяется значением критериев:
К
1 - качество дачи;
К
2 - расстояние до города;
К
3 - цена.
Диапазон значений для первого параметра решения (качество дачи), на основании
которого определяется критерий К1 , заданы равным [20; 100] (измеряется в процентах). Для
определения многомерной функции полезности U ( k1 ,k2 ,k3 ) и одномерная функция U1( k1 ) на
интервале [20,100] заданы следующие значения (дискретные значения), для некоторых
значения функций будут вычисляться: 20, 40, 60, 80, 100.
Диапазон значений параметра «расстояние до города», на основании которых
определяются значения критерия К2 , задан в виде [20;120]. Дискретные значения, для которых
определяются значения функций U ( k1 ,k2 ,k3 ) и одномерная функция U 2 ( k2 ) заданы
следующими: 20,40, 60, 80, 100, 120 (понятно, что чем расстояние до города ниже, тем
полезность больше, поэтому требуется использовать величину, обратную критерию
«расстояние до города»).
Диапазон значений параметра «цена», на основании которых определяются значения
критерия К3 , задан в виде [20;70]. Дискретные значения, для которых определяются значения
функций U ( k1 ,k2 ,k3 ) и одномерная функция U3( k3 ) заданы следующими: 20,30, 40, 50, 60, 70
(понятно, что чем цена ниже, тем полезность больше, поэтому требуется использовать
величину, обратную критерию «цена»).
Для сформированных диапазонов значений критериев необходимо определить
дискретные значения одномерных функций полезности U1( k1 ) , U 2 ( k2 ), U3( k3 )
На основании полученных значений одномерных функций полезности U1( k1 ) ,U 2 ( k2 ),
U3( k3 ) должны быть определены аналитические формы этих функций (для постановки в них
произвольных значений рассматриваемых параметров, характеризующих решения). Для них
должны
быть
заданы
следующие
аналитическиеформы:
U
( k
) a k
1
b ( k
1
)
2
,
1
1
1
1
U
( k
2
) a k
2
b ( k
2
)2 , U ( k
) = a k + b ( k )
2
. Для определения
коэффициентов
в
2
2
2
3
3
3
3
3
3
приведенных аналитических функциях U1( k1 ) , U 2 ( k2 ), U3( k3 ) необходимо применить метод
наименьших квадратов
Т.к.
аналитические формы выражений для U1( k1 ) и U 2 ( k2 ) получены, а многомерная
полезность
U ( k
1
,k
2
,k
3
)
является аддитивной
функцией, тогда
для заданных в таблице
значений параметров определить эффективное решение.
Вариант решения
Критерии
k1
k2
k3
x
1
40
50
30
x
2
80
30
50
x
3
50
90
45
x
4
75
40
60
x
5
60
80
40
38
5. Контрольные вопросы
5.1. В чем состоит понятие замещения по полезности и его связь с уступкой и приращением?
5.2. Какие решения являются эквивалентными по полезности?
5.3. Что из себя представляют кривые безразличия?
5.4. Каким образом предпочтения ЛПР интерпретируются с точки зрения кривых безразличия?
5.5. Каким образом используется принцип замещения при построении функции полезности?
5.6. Что такое коэффициент замещения по полезности и в какой точке кривой безразличия он
является максимальным?
5.7. Что такое аддитивная функция полезности и в чем заключаются условие ее
существования?
5.8. В чем заключается условие соответственных замещений и что оно определяет?
5.8. В чем заключается алгоритм формирования кривых безразличия с учетом аддитивных
свойств многомерной функции полезности?
5.10. Какие результаты построения кривых безразличия будут использоваться для
дальнейшего принятия решений?
5.11. В чем заключается алгоритм процедуры определения эффективных решений с
использованием многомерной функции полезности?
39
ЛАБОРАТОРНАЯ РАБОТА №4
ИССЛЕДОВАНИЕ МЕТОДОВ РЕШЕНИЯ МНОГОКРИТЕРИАЛЬНЫХ ЗАДАЧ
ПРИНЯТИЯ РЕШЕНИЙ НА ОСНОВЕ ПОСТРОЕНИЯ МНОЖЕСТВА ПАРЕТО
1. Цель работы: исследовать способы формирования множества Парето-оптимальных
решений и определения эффективных решений в этом множестве
2. Теоретическое введение
2.1. Общие понятия о формировании множества Парето-оптимальных решений
Для формализации задачи формирования множества Парето-оптимальных решений в
множестве допустимых решений в рассмотрение введены следующие обозначения:
1) X - множество допустимых решений многокритериальной задачи определения
эффективных решений;
2) fi ( i = 1,m ) – локальные частные критерии, соответствующие целям функционирования
системы, тогда f = ( f1 , f 2 ,.., f m ) - векторный критерий принятия решений; для определения
значений векторных оценок f = ( f1 , f 2 ,.., f m ) в рассмотрение введено обозначений
m
y = ( f1 , f 2 ,.., f m ) , тогда Y - критериальное пространство значений векторного критерия f ,
используемого при выборе решений;
Таким образом рассматривается задача принятия решений при многих критериях, при
этом скалярные критерии fi ( i = 1,m ) образуют векторный критерий
f .
Способ определения наилучших вариантов (решений) при многих критериях
предполагает определение множества Парето в пространстве допустимых решений Х.
Для идентификации (определения) множества эффективных решений в рассмотрение
введено отношение предпочтения вида:
x
i
x
j
,
которое
предполагает,
что решение
xi
является более предпочтительным, чем
решение
x
j
в
множестве
X .
По
аналогии
для
значений y оценок векторного критерия
f (x)
введено отношение
≥,
т.е.
y
1
≥
y
2
либо
f (x1 ) f (x2 ) , где y1 и
y2 –соответствующие значения оценок векторного критерия
f
для
решения
x
1
и
x
2
.
В общем виде (для m критериев) отношение
для значений
y
1
и
y2
(где
y1 и
y2
соответствующие значения векторных оценок), либо для значений векторов
f

x
1

и
fx2
выполняется в
том случае, если
f
i
( x
1
)
≥
f
i
( x
2
)
и хотя
бы
для
одного
из критериев
f
j
( x
1
)
≠
f
j
( x
2
)
. Таким образом, для случая m 2 имеем:
f ( x1 ) ≥ f ( x2 ) , если f1 ( x1 ) ≥ f1 ( x2 )
и f2 (x1 ) f2 (x2 ) , то f1( x1 ) > f1( x2 )
и
f
2
( x
1
)
≥
f
2
( x
2
)
(соответственно,
f1( x1 ) > f1( x2 ) и
f2 (x1 ) f2 (x2 ) ,
либо
f1 (x1 ) f1 (x2 )
и
f
2
(
x
1
)

f
2
(
x
2
)
,
а
также
f
1
(
x
1
)

f
1
(
x
2
)
и
f
2 ( x1 ) > f 2 ( x2 ) либо f1 (x1 ) f1 (x2 ) и f2 (x1 ) f2 (x2 ) ).
Так как
связь между решениями xi
и значениями yi
векторного критерия
f ( xi )
является однозначной, тогда при реализации
f ( x
i
)
≥
f ( x
j
)
выполняется
отношение
предпочтения
в
виде
xi x j .
Тогда решение xi
доминирует
решение x j , если по
всем
критериям решение xi
не хуже решения x j
(отношение "не хуже" имеет вид
),
а по одному
критерию
x
i
строго
лучше
x j .
Данное
заключение в формализованной форме
имеет
следующий
вид:
f1 ( xi ) ≥ f1 ( x j ) ,
f
2
( x
1
)
≥
f
2
( x
2
)
,..,
f
i
( x
1
) > f
i
( x
2
)
,..,
f
m
( x
1
)
≥
f
m
( x
2
)
. В
рассматриваемом случае доминирование решения
x
j
решением
x
i
является однозначным. В
основу приведенных рассуждений положена аксиома Парето о предпочтениях ЛПР: «Лицо,
40
принимающее решения, стремится получить большие значения всех компонент векторного
критерия».
В соответствии с введѐнными отношениями предпочтения и доминирования может быть
определено условие формирования множества недоминируемых решений:
– если ∃/x j такого, что x j xi , то xi является недоминируемым решением.
Понятно, что в соответствии с этим условием можно сформировать множество
недоминируемых решений. Однако, в силу того, что выполняется решение
многокритериальной задачи оптимизации, не все решения могут быть связаны отношением
предпочтения (доминирования), т.е. не к каждой паре решений x1 и x2 ( x1 , x2 ∈X ) может
быть применено отношение предпочтения. В общем виде (для m критериев) данные
утверждения могут быть прокомментированы следующим образом.
Решение xi не доминирует решение x j , а x j не доминирует решение xi , если:
f1 ( xi ) ≥ f1 ( x j ) , f 2 ( x1 ) ≥ f 2 ( x2 ) ,.., fi ( x1 ) < fi ( x2 ) ,.., f m ( x1 ) ≥ f m ( x2 ) ;
(1)
f1 ( xi ) ≤ f1 ( x j ) ,
f 2 ( x1 ) ≤ f 2 ( x2 ) ,.., fi ( x1 ) > fi ( x2 ) ,.., f m ( x1 ) ≤ f m ( x2 ) .
В этом случае решения
xi
и
x j
(2)
являются несравнимыми с
использованием
отношения
предпочтения. Таким образом, могут быть выделены решения,
которые являются
недоминируемыми какими-либо решениями множества Х, т.к. решения xi и x j
несравнимы,
поэтому недоминируемы.
Для случая двух критериев f1 и f 2 условие (1) может быть представлено в следующем
виде:
f1 ( xi ) ≥ f1 ( x j ) и f 2 ( xi ) < f 2 ( x j ) ,
(4)
Либо
f1 ( xi ) > f1 ( x j ) и f 2 ( xi ) ≤ f 2 ( x j ) .
(5)
По аналогии условие (2) для двух критериев примет следующий вид:
f1 ( xi ) ≤ f1 ( x j ) и f 2 ( xi ) > f 2 ( x j ) ,
(6)
либо
f1 ( xi ) < f1 ( x j ) и f 2 ( xi ) ≥ f 2 ( x j ) .
(7)
Те решения xi и x j , для которых выполняются либо условия (4), (5) либо условия (6),
(7) не могут быть сравнимы с использованием отношения .
Таким образом, если условия xi x j либо x j xi не выполняются, то решения xi и x j
входят в так называемую границу Парето допустимого множества решений. Границе Парето
поставлено в соответствие множество решений xi ∈X , которые не могут быть сравнимы
между собой с помощью отношения предпочтения и, как следствие, являются
недоминируемыми. Элементы xi ∈X , которые являются недоминируемыми и не сравнимыми
с другими решениями с использованием отношения , образуют множество Парето. Парето -
границу множества X допустимых решений обозначим как P( X ) . Способ формирования
Парето- границы определяет аксиома о доминируемости (Парето – доминируемости) решений.
Аксиома Парето о доминируемости решений.
Если xi x j , то x j P( X ) , где x j – решение, доминируемое решением xi .
41
Тогда решение x j не может входить в Парето-множество (лежать на Парето-границе). И,
соответственно, если
∃x
j такой, что x j xi , то xi P( X ) . Тогда Парето-множество
содержит так называемые Парето - оптимальные решения.
Т.к. сформулировано условие формирования Парето-границы P( X ) множества
допустимых решений X , тогда принцип Эджворта – Парето [8,9] определяет способ
идентификации множества эффективных решений: выбираемые эффективные решения будут
Парето-оптимальными. Т.е. эффективные решения в множестве Х нужно выбирать только
среди Парето-оптимальных решений. В результате эффективное решение (множество
эффективных решений) будет выбираться (определяться) в множестве Парето-оптимальных
решений (эффективное решение будет выбираться на Парето- границе).
Таким образом, если решение xi ∈P( X ) является недоминируемым ни одним из
решений x j ∈X (т.е. условие x j xi не выполняется ни для одного x j ∈X ) и не может быть
сравнимо с другими решениями, принадлежащими этой границе, с использованием отношения
предпочтения , тогда решение добавляется в Парето – границу (в Парето – множество). При
этом оно недоминируется другими решениями, уже находящимися на границе.
Решение добавляется в Парето-границу, если нет решений, которые бы его
доминировали, и, соответственно, удаляется из границы, если оно доминируется
рассматриваемыми на данном шаге алгоритма решениями. Данная формулировка целиком
согласуется с формулировкой аксиомы о доминировании (о Парето – границе), приведѐнной в
[9]: если для какой-либо пары решений xi и x j выполняется f ( x i ) ≥ f ( x j ) (соответственно
xi x j ), то x j P(x) .
Тогда доминируемое решением xi решение x j не может быть включено в Парето-
границу, а для решения xi выполняется условие: ∃/x j такого, что x j xi , xi , x j ∈X
В связи с тем, что в реализацию метода многокритериальной оптимизации положен
принцип Эджворта – Парето (выбор эффективных решений на Парето-границе (в множестве
Парето)), то возникает вопрос по поводу существования этого множества (т.к. требуется,
чтобы P(X ) ≠).
В соответствии с заключениями, приведѐнными в [9], при условии, что множество X
является конечным, множество P( X ) является непустым. Допустим, что решаемая задача
является задачей с конечным и счетным множеством возможных решений X , то P( X ) ≠ .
Таким образом, выполнение поиска эффективных решений многокритериальной задачи
осуществляется путѐм реализации двух этапов:
1) формирование множества Парето-оптимальных решений (Парето-границы P( X ) )
множества допустимых решений X ;
2) определение на Парето-границе тех эффективных решений, которые позволят
максимизировать (в наибольшой степени) все критерии в многокритериальной задаче (в
соответствии с аксиомой о предпочтениях ЛПР).
Так как рассматриваемая задача предполагает наличие конечного множества
допустимых решений, при поиске эффективных альтернатив реализуется переход от одного
решения к другому, тогда должны быть определены особенности формирования Парето-
границы P(X ) множества допустимых решений X .
Выяснение особенностей формирования Парето-границы (определения решений,
входящих в Парето-границу) выполняется на основе Рис. 1 с использованием аксиом о
предпочтениях ЛПР, о доминировании решений (понятий доминируемых и недоминируемых
по Парето решений). Для Рис. 1 рассуждения, определяющие особенности формирования
Парето-границы, строятся следующим образом:
1) при формировании решения x2 решение x1 исключается из рассмотрения, т.к. x2 x1 (в
результате x1 не может входить в Парето-границу);
42
Рисунок 1 – Особенности определение решений, входящих в Парето-границу множества
допустимых решений X
2) при переходе от решения x2 к решению x3 сравнение их с использованием отношения x2 f1x3 и f
2x2 f 2x3; в соответствии с
этимпредпочтенияневозможно,т.к.f1
решения x2 и x3 могут быть включены в границу Парето ( x2 ∈P( X ), x3 ∈P( X ));
3) переход от решения x3 к решению x4 обуславливает эквивалентность решений по одному из
критериев ( f1x3 f1x4) и доминирование решением x3 решения x4 по другому критерию
( f 2x3 f 2x4) , в соответствии с этим x3 x4 (по введѐнному выше понятию
отношения предпочтения (доминирования) решений) и решение x4 P( X ) (в соответствии с
аксиомой);
4) при переходе от решения x4 к решению x5 должна быть исследована возможность
включения решения x5 в Парето- границу (при условии, что решение x4 исключено из неѐ); т.к.
множество Парето P( X ) образуют только те решения, которые не сравнимы с использованием
отношения , а решение x4 исключено из P( X ) , тогда должно быть выполнено сравнение
решения x5 с решением x3 , входящим в P( X ) , т.к. (в соответствии с
Рис. 1) связывание решений x3 и x5 отношение невозможно, то x5 ∈P( X ) , также как x3 ∈P( X
) ;
5) по аналогии решение x6 не может быть связано с решением x5 отношением предпочтения ,
поэтому на данном этапе рассуждений x6 должно быть включено в P( X ) ( x6 ∈P( x ) );
6) переход от решения x6 к решению x7 обуславливает эквивалентность решений по
критерию f 2 ( f 2 ( x6 ) = f 2 ( x7 ) ) и доминирование решением x7 решения x6 по критерию f 1 (
f1( x7 ) > f1( x6 ) ), тогда выполняется x7 x6 и в соответствии с аксиомой о Парето- границе x6
должно быть исключено из множества P( X ) ; аналогичные рассуждения, касающиеся решения
x8 , которое не может быть связано с решением x7 отношением , позволяют сделать вывод о
том, что x8 ∈P( X ) .
Выполненные рассуждения касаются доминирования и не доминирования решений xi
(i 1,8) , они позволили сформировать множество Парето в следующем виде:
P( X ) = {x2 , x3 , x5 , x7 , x8 }.
43
В общем виде при переходе от решения xi
к решению xi1
возможны следующие
ситуации, определяющие реализацию отношения
для них: 1) xi
xi1 ; 2) xi1
xi ; 3)
xi
x
i+1
и
x
i+ j
xi .
Понятно, что в первом случае xi1 P( X ) , во втором – xi P( X ) , в третьем –
xi P(x)
и xi+1 ∈P( X ) на рассматриваемом текущем шаге формирования Парето-границы.
Таким образом, в основу формирования множества P( X ) положена аксиома «о
предпочтениях ЛПР» и аксиома «о Парето- границе множества X ».
Следует отметить, что вид границы Парето (выпуклость либо вогнутость) не
рассматривается, определяется принадлежность (возможность включения) следующего
рассматриваемого решения Парето-границе и необходимость исключения предыдущего
рассматриваемого решения из этой границы в случае его доминирования. При этом
принадлежность решения Парето-границе определяется на основе рассматриваемых условий
доминирования и недоминирования решений (условий для отношений предпочтения/
доминирования). Т.к. в соответствии с принципом Эджворта – Парето эффективные решения
принадлежат Парето-границе, тогда должен быть сформирован способ определения наиболее
эффективного решения (эффективных решений) среди тех, которые принадлежат P(X ) . В
литературе [7-9] изложены различные способы определения эффективных решений, выбор
которых будет обеспечивать выполнение аксиомы «о предпочтениях ЛПР» (выбор решения, в
наибольшей степени максимизирующего все используемые критерии) [9].
Наиболее развитыми методами определения эффективных решений на Парето-границе
являются: метод идеальной точки (метод точки утопии), метод последовательных уступок.
Рассмотрим аппарат этих методов с точки зрения решения задачи принятия решений при двух
критериях.
В основу первого способа определения эффективного решения в множестве Парето (на
Парето-границе) положено понятие идеальной точки (точки утопии) и метрики (расстояния)
от текущего рассматриваемого решения до этой идеальной точки (Рис.2.).
Рисунок 2 – Определение эффективных решений на Парето-границе с использованием метода
идеальной точки
Точка утопии – это точка с координатами ( f1m ax, f 2m ax ) , где
f
i
m ax
(
i

1,2)
- максимально
возможные значения каждого из критериев. Значения
f
i
m ax
(
i

фиксируются как значения
1,2)
соответствующих решений с координатами ( f 1max , f 21 ) и ( f11 , f 2max ), т.е. решений с
максимальными значениями соответствующих критериев.
В качестве меры удалѐнности точки критериального пространства от точки утопии для
текущего рассматриваемого решения x используется эвклидова метрика в виде:
r( f m ax f )2 ( f m ax f
)21 2
44
Очевидно,
что эффективным выбирается решение
x
*i
∈
P( X )
, для которого выполняется
условие: x* = arg min
r . Таким
образом, для каждого
решения
x
i
∈
X
определяется
i
x
i
∈
P
(
X
)
x
i
принадлежность
его
к
Парето-границе (множеству Парето
P( X )),
затем в случае, если
x
i
∈
P
(
X
)
, тогда
для
решения
x
i
вычисляется расстояние
r
точки
утопии
( f
m ax
, f
m ax
) ,
x
i
1
2
выполняется сравнение
полученного для решения xi
расстояния
до точки утопии
с
расстоянием текущего локально эффективного решения
x
*j
.
Если для текущего решения
xi
расстояние
r
x
i
является меньшим, чем
r
x
*
j
, то решение
x
i
становится локально эффективным
( x*j = xi ).
Тогда для задачи определения эффективных решений на Парето-границе при наличии
двух критериев (при векторном критерии) разработан алгоритм соответствующей процедуры
принятия решений. Для реализации алгоритма принятия решений при двух критериях в
рассмотрение введены следующие обозначения:
1) P1– множество значений критерия f1 для решений xi ∈P( X ) (т.е. f1( xi )∈P1 ); P2 –
множество значений критерия f 2 для решений xi ∈P( X ) (т.е. f2 ( xi )∈P2 xi ∈P( X ) );
2) k p – количество элементов в множествах P1 и P2 ;
3) i – индекс текущих рассматриваемых элементов в множествах P1 и P2 ;
4) P1i , P2i – i-е текущие рассматриваемые элементы множеств P1 и P2 ;
5) j– индекс рассматриваемого решения из множества Х, принадлежность которого Парето-
границе будет исследована на текущем шаге алгоритма;
6) xi - некоторое текущее решение, принадлежность которого к Парето-границе определена на
предыдущих шагах алгоритма и значения критериев которого f1( xi ) P1i и f 2 ( xi ) P2i сри
исследуется возможность включения его в Парето-границу, решению xi соответствуют
значения критериев f1( xi ) и f 2 ( xi ) .
7) x j - некоторое текущее решение ( x j X ), для которого исследуется возможность
включения его в Парето-границу, решению x j соответствуют значения критериев f1 ( x j ) и
f 2 ( x j ) ;
5) s – индекс текущего шага алгоритма.
7) n– количество решений в множестве Х (мощность множества решений Х).
Первоначальная инициализация введенных параметров, выполняемых на первом шаге
алгоритма (при s = 1) выглядит следующим образом: 1) P1(1) 0 ; P2(1) 0 ; 2) kp(1) 0 .
В случае рассмотрения первого решения x1 (при P1 0; P2 0; kp 0 ), преобразование
введенных параметров выполняется в соответствии с выражениями вида (при этом индекс
шага алгоритма s 2 ):
P1( 2 ) P1( 1 ) { f1( x1 )}; P2( 2 ) P2( 1 ) { f 2 ( x1 )};
kp(2) kp(1)1.
Для решения
x
1
выполняется
вычисление
расстояния
до
идеальной
1
r
x
1


( f
1m ax

f
1
(x
1
))
2

( f
2m ax

f
2
(x
2
))
2

,
после чего
реализуется присваивание rx*
2
соответственно, x*
x .
Т.е. локально
эффективным решением
на
начальной
1
реализации алгоритма является решение x1 .
точки
rx1 и,
стадии
Для всех последующих решений xi ( i = 2,n ) шаги алгоритма принятия решений при двух
критериях предполагают: определение принадлежности xi ( i = 2,n ) Парето-границе
(определение, что xi ∈P( X ) ), вычисление расстояния rxi до точки утопии (точки
45
( f1m ax, f 2m ax ) ), определение выполнения условия минимума значения метрики до этой точки
x
*
= arg
min r
(фиксация локально эффективного и глобально эффективного решений).
i
x
i
∈
P
(
X
)
x
i
Если kp соответствует количеству элементов, включенных в результате реализации алгоритма
в Парето-границу, тогда возможность включения в эту границу нового
x j -го решения
исследуется путем сравнения его значений критериев f
1
и f
2
(значений f
1
( x
j
)
и f
2
( x
j
) ) со
значениями этих критериев для решений xi (с его значениями f1( xi ) P1i
и
f
2
( x
i
)

P2
i
,
при этом i 1,k p ).
В этом случае алгоритм определения эффективных решений в множестве Х на основе
метода идеальной точки имеет следующую последовательности шагов:
1) значения индекса j решения x j X , возможность добавления которого в Парето-границу
исследуется на текущем шаге алгоритма, задается равным 2 (j=2);
2) значение индекса i текущего рассматриваемого решения в множестве P(Х) (т.е. xi P( X ) )
задается равным 1 ( i 1 ); для рассматриваемого элемента xi , значения критериев равны
соответственно P1i , P2i ;
3) если для решения x j значение f1 (x j ) P1i , тогда решение x j доминирует решение xi по
критерию
f
1
(x
j
f1 xi ) , которому соответствует значение
( f
1
(x
i
)

P1
i
)

P1; если условие
доминирования
решением x j решения xi
по критерию f1
выполняется, тогда необходимо
реализовать проверку условия ( f 2 (x j ) P2i
f 2 (xi ) | xi
P( X ) ); при невыполнении условия
f
1
(x
j
)

P1
i
требуется осуществить переход к шагу 8;
4) если ( f 2 (x j ) P2i f 2 (xi ) | xi P( X ) ), то рассматриваемое решение
x j не может быть
сравнимо с использование отношения предпочтения
с решением xi , которому
соответствуют значения
f
1
(
x
i
)

P
1
i
и
f
2
(
x
i
)

P
2
i
(т.е.
x
j
x
i
и x
i
x
j
), выполняется переход
к шагу 15;
5) если
(
f
2
(
x
j
)

P
2
i

f
2
(
x
i
) |
x
i

P
(
X
)
), то (x
j
x
i
) ,
где
f
1
(x
i
)

P1
i
и
f 2 (xi ) P2i , тогда
xi не
может
входить в Парето-границу, т.к. является доминируемым,
поэтому значения
f1( xi ) P1i
и
f 2 ( xi ) P2i необходимо исключить из множеств
P1 и P2 следующим
образом:
P1(s1) P1(s) \ {P1i } ;
P2(s1) P2(s) \ {P2i };
6) смещение элементов массивов P1 и P2 с индексами (i+1),…,kp в позиции с индексами
i,…,kp-1 (изменение вида массивов (множеств) P1 и P2 после исключения из них значений
f1 (xi ) P1i и f 2 (xi ) P2i , соответствующих решению xi , доминируемому решением x j );
при исключении i-ых элементов из множеств P1 и P2 на их место должны быть размещены
значения P1i1 и P2i1 , поэтому индекс текущих рассматриваемых элементов в множествах
P1 и P2 изменяться не должен;
7) если i=kp, тогда изменение количества решений в Парето-границе (множестве Р(Х)) kp=kp-
1 и переход на шаг 15; если i<kp, тогда изменение количества решений в Парето-границе
(множестве Р(Х))
kp=kp-1 и
переход на шаг 3;
8)
если условие (
f
1
(x
j
)

P1
i
|
x
i

P
(
X
)
)
выполняется, то решение xi
доминирует решение
x
j
по критерию
f
1
(
x
i f
1
x
j
), должна
быть выполнена проверка
условия f 2 (x j ) P2i
46
( xi
P(X));
если условие
f
1
(
x
j
)

P
1
i
выполняется, то реализуется переход к шагу 9;
при
невыполнении условия
f
1
(
x
j
)

P
1
i
реализуется переход к шагу 11;
9)
выполняется проверка условия
f
2
(
x
j
)

P
2
i
,
если это условие выполняется, то решения
x j
и xi P( X ) не могут быть сравнимы с использованием отношения предпочтения
( xkp xi и xi xkp ), выполняется переход к шагу 15;
10)
реализуется проверка условия
f
2
( x
j
)

P2
i
, если условие
f
2
( x
j
)

P2
i
выполняется, то
решение xi
доминирует
решение
x j по
векторному критерию
f
( x
i f
x
j
),
т.е.
рассматриваемое решение x j не может быть включено в Парето-границу;
тогда должно быть
определено следующее решение
x j , его значения критериев
f
1
(
x
j
)
и
f
2
(
x
j
)
, выполнен
последующий анализ возможности включения его в Р(Х), для этого реализуется переход на
шаг 19;
11) выполняется проверка условия f1 (x j ) P1i (при реализации перехода на этот шаг данное
условие выполняется априори); реализуется проверка условия
f
2
(
x
j
)

P
2
i
,
если
условие
(
f
2
(
x
j
)

P
2
i
) является истинным, то решение
x j
доминируется решением
x
i
(которому
соответствует значение
f
2
(x
i
)

P2
i
), поэтому решение
x
j
не может быть включено в Парето-
границу, реализуется переход к шагу 19;
если
f 2 (x j ) P2i , то решение x j
эквивалентно
решению
xi
(переход
к
решению
x j
не приводит к улучшению значения векторного
критерия
и анализируемое
решение
x j
не включается
в Парето-границу),
выполняется
переход к шагу 19;
12) выполняется проверка
f
2
(
x
j
)

P
2
i
, если это условие является верным, то по критерию
f
2
решение
x j
доминирует решение xi
(
x
j
f 2 xi ); т.к. по критерию
f1 решения
x j и
x
i
эквивалентны и
x
j f
2
x
i
, то решение x
j
доминирует решение
x
i
по векторному критерию
f
( x
j f
x
i
или
x j xi ),
следовательно
решение
x
i
должно быть
исключено
из Парето-
границы, а его значения
f
1
(x
i
) P1
i
и
f
2
(x
i
)

P2
i
из множеств Р1 и Р2 соответственно, тогда
преобразования этих множеств выполняется с использованием выражений:
P1(s1) P1(s) \ {P1i } ;
P2(s1) P2(s) \ {P2i };
13) смещение элементов массивов P1 и P2 с индексами (i+1),…,n в позиции с индексами
i,…,n-1 (изменение вида массивов (множеств) P1 и P2 после исключения из них значений
f1 (xi ) P1i и f 2 (xi ) P2i , соответствующих решению xi , доминируемому решением x j );
при исключении i-ых элементов из множеств P1 и P2 на их место должны быть размещены
значения P1i1 и P2i1 , поэтому индекс текущих рассматриваемых элементов в множествах
P1 и P2 изменяться не должен;
14) если i=kp, тогда изменение количества решений в Парето-границе (множестве Р(Х))
kp=kp-1 и переход на шаг 15; если i<kp, тогда изменение количества решений в Парето-
границе (множестве Р(Х)) kp=kp-1 и переход на шаг 3;
15) изменение индекса i текущих рассматриваемых элементов P1i и P2i множеств P1 и P2
следующим образом: i=i+1, если i kp , то выполняется переход к шагу 3; если i kp, то
выполняется переход на шаг 16;
16) значения критериев f1 и f 2 для анализируемого решения x j добавляются в множества P1и
P2 соответственно (само решение x j принадлежит Парето-границе P( X ) ):
47
P1(s1) P1(s)∪{ f1 (x j )} ;
P2(s1) P2(s)∪{ f 2 (x j )} ;
kp( s + 1) = kp( s ) + 1 ;
17) для решения x j ∈ P( X ) вычисляется значение расстояния rx j до точки утопии:
r ( f max - f (x ))2 ( f max - f (x ))21 ;
2
x j 1 1 j 2 2 j
18) реализуется сравнение полученного значения со значением rx* текущего эффективного
решения, если r
*
r , то:
r
*
r
x
*

x
j
(т.е. выполняется сохранение (буферизация)
x
x j
x
x j ;
текущего локального эффективного решения);
19) изменение индекса текущего рассматриваемого решения j следующим образом: j=j+1;
если j n , то переход к шагу 2; в противном случае – шаг 20;
20) останов алгоритма (окончание алгоритма).
После окончания алгоритма множества (массивы) P1 и P2 содержат значения всех решений xi
( i 1, k p ), которые входят в Парето-границу (множество P(X)), а параметр x*
представляет собой то решение, которое ближе всего находится к точке утопии.
Предложенный алгоритм может быть модифицирован следующим образом:
1) определение координат идеальной точки (координат точки утопии);
2) формирование Парето-границы для множества Х (определение множества P(X) решений и
соответствующих им значений критериев f1 и f2);
3) определение среди элементов множества Р(Х) такого решения x*j , расстояние rx j до
идеальной точки ( f1m ax, f 2m ax ) для которого будет являться минимальным.
Метод уступок при определении эффективного решения x*j также предполагает, что
первоначально должна быть сформирована Парето-граница, затем, начиная от решений с
координатами ( f1m ax , f 21 ) и ( f12 , f 2m a x ) , выполняются последовательные уступки по
каждому из критериев:
1) для точки ( f1m ax , f 21 ) – уступки по критерию f1 для получения приращения по критерию f2;
2) для точки ( f12 , f 2m ax ) – уступки по критерию f2 для получения приращения по критерию f1.
Порядок последовательных уступок по критериям для поиска эффективных решений на
Парето-границе комментирует Рис.3.
Рисунок 3– Реализация процедуры метода последовательных уступок
48
Реализация метода уступок предполагает, что по каждому из критериев может быть
выполнена уступка (в значении этого критерия) для получения приращения по другому
критерию. Т.е. может быть выполнен переход от одного решения к другому, который
гарантирует при уменьшении значения одного из критериев увеличение значения другого
критерия. Реализация метода предусматривает переход между решениями на Парето-границе
при анализе уступок и приращений критериев f1 и f2. Реализация метода последовательных
уступок позволит:
1) при переходе от решения с координатами ( f12 , f 2m ax ) путем выполнения уступки по
критерию f2 получить приращение по критерию f1;
2) при переходе от решения с координатами ( f1m ax , f 21 ) путем выполнения уступки по
критерию f1 получить приращение по критерию f2.
При этом, т.к. критерии f1 и f2 являются равными по важности, то величины приращений
по каждому критерию (размеры приращений по критериям) должны быть если не
одинаковыми, то хотя бы сравнимыми друг с другом (сравнимыми с точки зрения их
величин). Если при реализации уступки по критерию f2
(при переходе из точки с
координатами
( f
12
, f
2m ax
) ) получено приращение критерия
f1,
обозначенное
1, а при
реализации уступки по критерию f1 (при переходе из точки с координатами
( f1m ax , f 21 ) )
получено приращение критерия f2, обозначенное2 ,
тогда желательной является ситуация
12.
Если1
2 (либо12 ), тогда на следующем шаге реализации алгоритма метода
уступка по критерию f2 для получения нового приращения
1 по критерию f1
может не
выполняться,
в то же время уступка по критерию f
1
для получения приращения2 по
критерию
f2
должна быть выполнена. Если12 (либо12 ), тогда уступка по
критерию f
1
для получения приращения2
по критерию f2 может не выполняться, при этом
уступка по f2
для получения приращения
1 по критерию
f1
должна быть выполнена.
Сформулированные рассуждения должны обеспечивать одинаковый порядок приращений по
каждому из критериев при реализации метода последовательных уступок.
Уступки по каждому из критериев будут продолжаться до тех пор, пока не будут
определена некоторая «общая» точка критериального пространства, достижимая как из точки
с координатами ( f1m ax , f 21 ) , так и из точки с координатами ( f12 , f 2m ax ) . Если такая точка не
может быть найдена (т.е. не может быть выполнено одинакового количества уступок по
каждому критерию для определения «общей» точки), тогда по каждому критерию выбираются
те повторяющиеся решения, которые уже были выбраны (рассмотрены) до этого при
реализации уступок по противоположному критерию, т.е.: 1) при реализации уступки по
критерию f2 определяется решение, которое уже было рассмотрено при выполнении уступок
по критерию f1; 2) при реализации уступки по критерию f1 выполняется переход к решению,
которое уже было рассмотрено при выполнении уступок по критерию f2. При этом
выполнение приведенных выше условий фиксируется одновременно, алгоритм реализации
дальнейших уступок останавливается, а в качестве действующего (эффективного) решения
может быть выбрано любое из двух решений, на которых алгоритм последовательных уступок
был остановлен.
Для реализации метода последовательных уступок при сформированной Парето-границе
в рассмотрение введены следующие дополнительные обозначения (дополняющие введенные
выше в рассмотрение обозначения):
1) P11– множество значений критерия f1 для решений xi ∈P( X ) (т.е. f1 (xi ) ∈ P11 ),
соответствующее множеству P1, используемое при реализации уступок по критерию f 2 из
точки ( f12 , f 2m ax ) , P21– множество значений критерия f 2 для решений xi ∈P( X ) (т.е.
49
f 2 (xi ) ∈ P21 ), соответствующее
множеству
P2 , используемое при реализации уступок по
критерию
f
2
из точки ( f 2 , f
m ax
)
;
1
2
2) P12 –
множество значений критерия f1
для решений
xi ∈P( X ) (т.е.
f1 (xi ) ∈ P12 ),
соответствующее множеству
P1, используемое при реализации уступок по критерию
f1 из
точки
(
f
1m ax
,
f
21
)
,
P22
– множество значений критерия f
2
для решений
x
i
∈
P( X
)
(т.е.
f 2 (xi ) ∈ P22 ), соответствующее
множеству
P2 , используемое при реализации уступок по
критерию
f
1
из точки ( f m ax , f 1 ) ;
1
2
3) i1 – индекс элементов векторов (множеств) PÕ1, P11, P21 при реализации уступок по
критерию f 2 ;
4) i2 – индекс элементов векторов (множеств) PÕ2 , P12, P22 при реализации уступок по
критерию f1 ;
5)
PХ1
–
множество
решений
xi ∈P( X ) ,
которым
соответствуют
значения
критериев
f
1
( x
i
)= P11
и
f
2
( x
i
)= P21
при реализации уступок по критерию f
2
из точки ( f 2 , f m ax )
i1
i2
1
2
4)
PХ 2
–
множество
решений
x
i
∈
P( X )
,
которым
соответствуют
значения
критериев
f
1 ( xi ) = P12i1 и f 2 ( xi ) = P22i2 при реализации уступок по критерию f1 из точки ( f1m ax , f 21 ) ;
8) delta1– параметр, определяющий общую величину приращения по критерию f1 при
реализации уступок по критерию f 2 при переходе из точки ( f12 , f 2m ax ) ;
9) delta2– параметр, определяющий общую величину приращения по критерию f 2 при
реализации уступок по критерию f1 при переходе из точки ( f1m ax , f 21 ) ;
Первоначальная инициализация значений параметров алгоритма выполняется
следующим образом: delta1=0; delta2=0. В соответствии с введенными обозначениями
порядок шагов алгоритма метода последовательных уступок следующий (при условии
сформированной предварительно Парето-границы и множеств P1 и P2 значений критериев f1(
xi ) P1i и f 2 ( xi ) P2i ):
1) на основе множества решений PX и множеств P1 и P2 значений критериев f1 и f2
реализовать инициализацию значений элементов множеств PХ1 и PХ 2 , P11 и P21, P12 и
P22 следующим образом: PХ1 PХ 2 PХ , P11 P12 P1, P21 P22 P2 (множества
PХ1, P11, P21 используются для реализации уступок по критерию f2, множества PХ 2 , P12 ,
P22 для реализации уступок по критерию f1);
2) элементы множеств (векторов) сортируются по: убыванию значений критерия f2 для
вектора (множества) P21, по возрастанию критерия f1 для вектора (множества) P12 ;
3) в соответствии с выполненным упорядочиванием элементов векторов (множеств) P21 и
P12 реализовать упорядочивание элементов связанных с ними векторов (множеств) PХ1 и
P11; PХ 2 и P22 ; тогда элементы всех векторов (множеств) будут упорядочены следующим
образом: а) P11, P21, PХ1 – в соответствии с убыванием значений критерия f2, б) P12 , P22 ,
PХ 2 – в соответствии с убыванием критерия f1 ; первые элементы в векторах P11 и
P21
имеют значения f12 и f 2max , а первый элемент в векторе PХ1 соответствует решению
x
j
с
координатами ( f12 , f 2m ax ) ; первые элементы в векторах P12 и
P22 имеют значения f1max
и
f
21 , а первый элемент в векторе
PХ 2
соответствует решению x
j
с координатами
(
f
1m ax
,
f
21
)
;
4) значение индекса i1 элементов в векторах (множествах) P11, P21, PХ1 задается равным 2
(i1=2);
5) значение индекса i2 элементов в векторах (множествах) P12 , P22 , PХ 2 задается равным
2 (i2=2);
6) реализуется сравнение элементов векторов (множеств)
P11
i1
и
P
12
i
2
,
P21i1 и
P22
i
2 ; если
выполняются условия
p11i1
=
p12i2
и
P
21
i1
=
P
22
i
2
, то
выполненные
уступки
позволили
получить некоторое «общее» решение (при упорядочивании векторов (множеств)
P11, P21 в
50
соответствии с убыванием значений критерия f2 и упорядочивании векторов (множеств) P12 ,
P22 в соответствии с возрастанием значений критерия f1 выполнение первого равенства
гарантирует автоматическое выполнение второго), в этом случае x* PX 1i1 , выполнить
переход на шаг 12;
7) если условия P11i1 = P12 i 2 и P21i1 = P22 i 2 не являются истинными (не выполняются), то
реализуется следующая проверка: P11i1 = P12i21 и P22 i 2 = P21i11 ; если данные условия
выполняются, то решение xi1 было рассмотрено ранее при выполнении уступки по критерию
f1 , решение xi 2 также было рассмотрено ранее при выполнении уступки по критерию f 2 ; в
этом случае «общее» решение, достигаемое путем реализации уступок по критериям f1 и f 2 ,
получено быть не может; в этом случае выполняется вычисление значений параметров delta1
и delta2 следующим образом:
delta1

delta1

(P11
i1
P11
i11
) ;
delta2

delta2

(P22
i 2
P22 i 21 ) ;
в том случае,
если delta1 delta2 , то в качестве эффективного решения выбирается решение
x* x1 ; при
delta1 delta2 эффективным выбирается решение x* x2 ; при
delta1

delta2
i1
i2
в качестве эффективного решения может быть выбран любой из элементов
x1
i1
либо
x2
i 2
множеств X1
и PX2 (т.е. x* px1
либо x* px2
), выполняется переход на шаг 10; при
i1
i2
невыполнении условий
P
11
i1
=
P12i2
1
и
P
22
i 2
=
P21i1
1
реализуется переход на шаг 8;
8) выполняется вычисление значений параметров delta1 и delta2 следующим образом:
delta1

delta1

(P11
i1
P11
i11
) ;
delta2

delta2

(P22
i 2
P22 i 21 ) ;
9) определение значений индексов элементов векторов (множеств) P11 и P21, P12 и P22
выполняется следующим образом:
если delta1 delta2 , то i2 i21, индекс i1 остается без изменения, реализуется переход на
шаг 7;
если delta1 delta2, то i1 i11, индекс i2 остается без изменения, реализуется переход на шаг
7;
если delta1 delta2, то i1 i11 и i2 i21, реализуется переход на шаг 7;
10) окончание алгоритма.
Реализация приведенного алгоритма позволяет определить единственное решение на
Парето-границе, эффективное с точки зрения приращений по критериям f1 и f 2 при
реализации уступок по критериям f 2 и f1 .
3. Программа выполнения работы
3.1. Для первого и третьего вариантов в соответствии с заданием необходимо реализовать
следующий порядок действий для выполнения лабораторной работы:
а) разработать процедуру определения на основе задаваемого множества решений Х и
соответствующих им значений критериев f1 и f 2 множества Р(Х), представляющего собой
Парето-границу Х;
б) разработать процедуру определения координат идеальной точки ( f1max , f 2max ) (точки
утопии);
в) разработать процедуру расчета расстояния rxi до точки утопии для координат текущего
рассматриваемого решения xi ;
г) разработать процедуру определения эффективного решения x* , расстояние rx* до которого
от идеальной точки ( f1max , f 2max ) является минимальным.
51
3.1. Для второго варианта в соответствии с заданием необходимо реализовать следующий
порядок действий для выполнения лабораторной работы:
а) разработать процедуру определения на основе задаваемого множества решений Х и
соответствующих им значений критериев f1 и f 2 множества Р(Х), представляющего собой
Парето-границу Х;
б) разработать процедуру определения решений xi с координатами точек ( f1max , f 21 ) и ( f12 , f
2max ) в критериальном пространстве;
в) разработать процедуру упорядочивания векторов (множеств) PX1, P11, P21 по убыванию
значений критерия f 2 , начиная от значения f 2m a x , векторов (множеств) PX2 , P12, P22 по
убыванию значений критерия f 1 , начиная от значения f 1m a x ;
г) разработать процедуру, реализующую переход между решениями в множестве (векторе)
PX1 при осуществлении уступок по критерию f 2 и приращении по критерию f 1 , в множестве
(векторе) PX2 при осуществлении уступок по критерию f 1 и приращении по критерию f 2 ;
кроме перехода между решениями в разрабатываемой процедуре требуется предусмотреть
контроль выполнения условий реализации уступок на каждом шаге алгоритма,
контролировать условие окончания процесса реализации перехода между решениями
(контролировать условие окончания процесса осуществления уступок при переходе между
решениями).
4. Задание на работу
Вариант 1. Требуется для задаваемого множества Х в виде: X = { xi ,i = 1,10 } выполнить
определение эффективных решений двухкритериальной задачи выбора с использованием
метода идеальной точки. Значения критериев f 1 и f 2 для соответствующих решений xi
( i = 1,10 ) сведены в матрицу, представленную ниже.
f1 f 2
x1
x2
x3
x4
x5
x6
x7
x8
x9
x10
3 2
4 5
5 3
8 3
6 2
3 8
6 4
2 5
6 4
2 5
Вариант 2. Требуется для задаваемого множества Х в виде: X = { xi ,i = 1,10 } выполнить
определение эффективных решений двухкритериальной задачи выбора с использованием
метода последовательных уступок. Значения критериев f 1 и f 2 для соответствующих
решений xi ( i = 1,10 ) сведены в матрицу, представленную ниже.
52
x1
x2
x3
x4
x5
x6
x7
x8
x9
x10
f1 f 2
3 2
5 6
5 3
8 4
6 2
3 8
6 4
2 5
9 2
3 9
Вариант 3. Требуется для задаваемого множества Х в виде: X = { xi ,i = 1,10 } выполнить
определение эффективных решений трехкритериальной задачи выбора с использованием
метода идеальной точки. Значения критериев f 1 , f 2 и f 3 для соответствующих решений xi
( i = 1,10 ) сведены в матрицу, представленную ниже.
x1
x2
x3
x4
x5
x6
x7
x8
x
x10
5. Контрольные вопросы
f1 f 2 f3
3 2 2
5 6 4
5 3 3
8 4 4
6 2 6
3 8 5
6 4 3
2 5 2
9 2 5
3 5 2
5.1. В чем заключаются условия доминирования вектора f (x j ) со стороны вектора f (xi )
(условие для выполнения отношения xi x j при многих критериях).
5.2. В чем заключаются условия, в соответствии с которыми решение xi несравнимо с
решением x j с использованием отношения предпочтения (при векторном критерии f).
5.3. В чем состоит смысл аксиомы Парето о предпочтениях ЛПР с точки зрения условия
доминирования вектора f (x j ) вектором f (xi ).
5.4. В чем заключается условие формирования Парето-границы множества решений Х с точки
зрения аксиомы Парето о доминировании решений, какой вид имеет формализация этого
условия.
5.5. Каким образом осуществляется определение эффективных решений в множестве Х с
точки зрения принципа Эджворта-Парето.
5.6. Каковы особенности определения решений, входящих в Парето-границу с точки зрения
аксиомы о предпочтениях ЛПР (для двухкритериальной задачи).
5.7. В чем состоит понятие идеальной точки (точки утопии) и как она используется при
определении эффективного решения на Парето-границе.
53
5.8. В чем состоит алгоритм метода построения Парето-границы множества решений Х
(определить обобщенно последовательность шагов).
5.9. Проверка каких условий включения текущего рассматриваемого решения в границу
Парето и каким образом реализуется в алгоритме метода формирования Р(Х).
5.10. Истинность каких условий в алгоритме метода формирования Р(Х) позволяет исключить
решение из Парето-границы.
5.11. Истинность каких условий в алгоритме метода формирования Р(Х) позволяет не
включать решение в Парето-границу.
5.12. Каким образом в методе идеальной точки выполняется выбор эффективного решения на
Парето-границе.
5.13. В чем состоит подход к определению эффективных решений в методе последовательных
уступок.
5.14. В чем заключается условие реализации на следующем шаге алгоритма уступки по
одному (либо по каждому) из критериев в одноименном методе.
5.15. В чем состоит алгоритм метода последовательных уступок при условии использования
сформированной Парето-границы.
5.16. Истинность каких условий позволяет выполнить остановку алгоритма метода
последовательных уступок.
5.17. В чем заключаются причины использования метода идеальной точки и метода
последовательных уступок при поиске эффективных решений на Парето-границе.
54
ЛАБОРАТОРНАЯ РАБОТА №5
ИССЛЕДОВАНИЕ ПРИМЕНЕНИЯ ТЕОРИИ ВАЖНОСТИ КРИТЕРИЕВ ДЛЯ
РЕШЕНИЯ ЗАДАЧИ ВЫБОРА АЛЬТЕРНАТИВ
1. Цель работы: исследовать применение аппарата теории важности критериев при
принятии решений по выбору альтернатив
2. Теоретическое введение
2.1. Общие понятия теории важности критериев
Основное понятие, используемое при решении многокритериальных задач – это
понятие относительной важности критериев. С точки зрения важности критериев определены
понятия «один критерий важнее другого», «критерии равноважны» (имеют одинаковую
важность), на основе этих понятий сформулирована качественная теория важности критериев.
Развитие качественной теории важности критериев определило
количественное сравнение
важности критериев (т.е. «во сколько раз один критерий важнее другого»).
Математическая модель задачи принятия решений при многих критериях и учете их
(критериев) важности имеет вид:
X – множество решений; K – векторный критерий; ,~ –
отношения предпочтения и безразличия ЛПР соответственно;
xi
- некоторое i-е решение,
характеризуется значениями критериев K j ( j =
1,m
)
;
K j – некоторый частный критерий. Тогда
векторный критерий К имеет вид
K

(K
1
, K
2
,...,
K
m
)
, т.е.
векторный критерий К – это
упорядоченный набор критериев. Тогда решение xi
характеризуется векторный его оценкой в
виде
K( x
)=(K
1
( x
),K
2
( x ),..., K
m
( x
)) . Через
K j
может
быть
обозначено множество
i
i
i
i
возможных значений критерия
K j ,
тогда K X
m
- множество всех векторных оценок,
= X K j
i=1
соответствующих возможным решениям, где X – декартово произведение множеств.
Пример постановки задачи многокритериального принятия решений.
Определено (задано) множество из 7 студентов, каждый из которых получил оценки по
4 предметам, тогда
X
=7, количество критериев равно 4, ki j –
оценки j-го критерия для i-го
студента (т.е. оценка для i-го студента по j-му предмету). Таким образом, X = { x1 ,x2 ,..., x7 } ,
шкала для каждого критерия имеет вид { 2,3,4,5 }. Полученные данные сведены в Таблицу 1.
Таблица 1. Скалярные оценки ki j критериев K j
для решений xi
( i
1,7
, j
1,4
)
Варианты
Критерии
K1
K 2
K 3
K
4
x
1
3
5
5
4
x
2
4
4
4
5
x
3
5
4
3
3
x4
3
5
3
5
x
5
4
2
4
5
x
6
3
5
3
5
x
7
5
3
4
3
55
Требуется выбрать лучшего по успеваемости студента из семи претендентов, учитывая
оценки по четырем предметам. Наряду с приведенными векторными оценками K( xi )
вариантов могут быть указаны возможные векторные оценки, тогда K X
4
= X K j , | K X |= 256 .
j=1
Сравнение вариантов осуществляется на основе их векторных оценок.
Варианты x4 и x6
являются эквивалентными ( x4 ~ x6 ).
Если черезобозначено отношение предпочтения, тогда для x2 и x5 является
верным:
( 4,4,4,5 ) ( 4,2,4,5 ) , т.к. для оценок k2 j ≥k5 j ( j = 1,4 ) , а по критерию k2 решение x2
строго
лучше решения x5
( k22 > k52 ). Таким образом, решение x2
является
предпочтительнее
решения x5 , так как по всем оценкам k2 j ≥k5 j , а по одной оценке вариант
x2 строго лучше
x5 ( k22 > k52 ), тогда
x2 x5 . Для векторных оценок ( 3,5,5,4 )
и ( 4,4,4,5 )
отношениене
реализуется, так как однозначно для них введенные условия предпочтения не выполняются.
Таким образом, ( 3,5,5,4 ) ( 4,4,4,5 ) и ( 4,4,4,5 ) ( 3,5,5,4 ) в итоге x1 x2 , x2 x1 и векторные оценки для
решений x1 , x2 и сами эти решения являются несравнимыми с использованием отношения .
Аналогичные выводы могут быть сделаны для пар решений: ( x1 , x3 ), ( x1 , x4 ),
( x1 , x5 ), ( x1 , x6 ), ( x1 , x7 ), ( x2 ,x3 ), ( x2 , x4 ), ( x2 , x6 ), ( x2 , x7 ), ( x3 ,x4 ), ( x3 , x5 ), ( x3 , x6 ), ( x3
, x7 ), ( x4 , x5 ), ( x4 , x7 ), ( x5 , x6 ), ( x5 , x7 ), ( x6 , x7 ) . Таким образом, приведенные в парах
решения являются несравнимыми по отношению . Так для решений x1 и x6 вектора оценок
имеют вид: ( 3,5,5,4 ) и ( 3,5,3,5 ) ,
для критерия
K
4
имеем k64 > k14 , хотя k1 j ≥k6 j ( j = 1,3 ) ,
поэтому x1
и x6 – несравнимы.
Если
x
i
x
j
выполняется,
то решение
x j
является доминируемым и не может быть
выбрано наилучшим.
Решение
x
*i
такое, что
∀
x
j
∈X , x j
x*i называется недоминируемым (оптимальным по
Эджворту-Парето). Множество таких решений – множество Эджворта-Парето обозначим как
X * . Решение x5 доминируется решением x2 , а все остальные решения являются
несравнимыми с использованием отношения , то для рассматриваемого случая имеем X * = { x1
,x2 ,x3 ,x4 ,x5 ,x6 ,x7 } при этом x4 ~ x6 . Т.к. | X * |> 1 , то не может быть выбрано решение x*i
являющееся наилучшим, поэтому должна быть привлечена дополнительная информация о
предпочтениях ЛПР. Для этого могут быть использованы следующие виды дополнительной
информации: 1) сведения об относительной важности критериев; 2) сведения о шкалах
критериев. Вид дополнительной информации обозначим как Ω , тогда ~ Ω и Ω – отношения,
вытекающие из этой информации.
Простейший способ скаляризации оценок критериев K j - это формирование
обобщенного критерия на основе аддитивной свертки следующим образом:
Φ = α1K1 + α2 K2 + ... + αm Km ,
(1)
где Φ – обозначение оценки обобщенного
(агрегированного) критерия,
αi ( i =
1,m
)
–
m
коэффициенты важности (веса) критериев, ∑ α j
=
1
.
j=1
В случае одинаковой важности критериев αi = 1 / m , а значение Φ для рассматриваемого
примера представляет собой средний балл. Т.к. в рассматриваемом случае разные дисциплины
могут иметь разную значимость, следовательно должна быть определена относительная
важность критериев и значения αi в выражении (1). Таким образом, базовые методы анализа (и
решения) многокритериальных задач основаны на свертывании набора исходных критериев
в один обобщенный (агрегированный, в частности используется аддитивная свертка)
критерий, имеющий вид взвешенный при помощи коэффициентов важности суммы исходных
56
критериев. Однако данные методы обладают рядом недостатков, ограничивающих их
использование.
При многокритериальном принятии решений должна быть учтена информация о
предпочтениях ЛПР (какой из критериев является более предпочтительным), выраженная в
виде сведений об относительной их (критериев) важности. При этом сведения об
относительной важности критериев должны быть строго формализованы.
2.2. Использование качественной теории важности критериев при принятии
решений
Определение важности критериев возможно в случае их (критериев) однородности, т.е.
критерии должны иметь сопоставимый вид. Условиями однородности критериев являются: 1)
наличие единой (общей) шкалы; 2) каждая градация шкалы должна отражать одинаковый
уровень предпочтений для каждого критерия.
Требованиями для градаций шкалы (требованиями к шкале) являются: 1) градации
нумеруются в порядке возрастания предпочтительности оценок критериев, для работы с
которыми используются шкалы; 2) номера градаций шкалы отражают упорядоченность
оценок критерия по предпочтениям; 3) с номерами градаций не могут быть выполнены какие-
либо арифметические операции для получения оценок предпочтений; 4) решения (для
реализации требования их однородности) оцениваются по всем критериям в единой бальной
шкале, при этом градации шкалы (отражающие степень предпочтения одного решения перед
другим) для всех критериев являются одинаковыми.
В этом случае используемая для определения оценок критерия (критериев) шкала
(шкалы) является качественной, все критерии являются однородными, т.е. имеют единую
порядковую шкалу. В случае неоднородных критериев (вес, стоимость, площадь) перед
сравнением этих критериев по важности их нужно привести к единой порядковой шкале с
одинаковым числам градаций q . Т.е. критерии не нормализуются по формуле ki / kmax , а их
исходная шкала разделяется на q частей таким образом, чтобы некоторый l-ый интервал
исходной шкалы соответствовал l-ой градации обобщенной шкалы. Тогда любое значение ki j
критерия K j ,
принадлежащее l-му
интервалу,
интерпретируется
как l-я
градация
формируемой единой шкалы.
Качественными оценками важности критериев являются суждения вида: «Критерий
K
i
важнее критерия K j ».
Для формализации важности
критерия K i
по отношению
(по
сравнению) с критерием
K j также как и для решений может быть использовано отношение
предпочтенияи безразличия (эквивалентности) ~.
Т.е.
выражение вида Ki K j
означает,
что критерий Ki
важнее (предпочтительнее) критерия K j
, а Ki ~ K j – что критерии являются
эквивалентными. Если K1 K2 и K2 ~ K3 , то критерий K1 важнее критерия, а критерии K2 и K3
эквивалентны.
Обозначим через K( x ) некоторую векторную оценку для решения x . Вид векторной
оценки:
K( x ) = ( K
1
( x ),K
2
( x ),.., K
m
( x ))
. Через
K
ij
( x )
обозначим векторную оценку решения
x , полученную из оценки K( x ) путем перестановки в ней i-ой и j-ой компонент (т.е.
k
i
и
k
j
).
Пример
формирования векторных оценок
K
ij
( x )
. Исходная векторная
оценка:
K( x ) = ( 5,4,3,4 )
,
K
14
( x ) = ( 4,4,3,5 )
,
K
23
( x ) = ( 5,3,4,4 )
.
Критерии
Ki
и K j
равно важны (эквивалентны с точки зрения важности)
если две
векторные оценки
K( x )
и K ij ( x ) одинаковы по
предпочтению. Т.е. если перестановка
значений i-го
и j-го критериев в векторной оценке K( x ) позволяет получить векторную
оценку K ij ( x ) эквивалентную K( x ).
57
Пример перестановки в векторе оценок критериев для равно важных критериев Ki и
K j . Исходная векторная оценка имеет вид K( x ) = ( 5,4,3,4 ) . Критерии K2 и K3 являются
равно важными (т.е. K2 K3 и K3 K2 ).
Тогда формируемая векторная оценка K 23 ( x ) = ( 5,3,4,4 ) будет являться эквивалентной
оценке K( x ), т.е. ( 5,4,3,4 ) ~ ( 5,3,4,4 ) при K 2 ~ K3 (где ~ – отношение эквивалентности, т.е.
критерии не различаются с точки зрения их важности и векторные оценки тоже не могут быть
сравнимы с использованием отношения , векторные оценки фактически не изменились при
перестановке значений критериев). Т.е. перестановка оценок k i и k j соответствующих
критериев позволяет получить для дальнейшего анализа вектор оценок K ij ( x ) , который
эквивалентен исходному вектору K( x ).
Пример перестановки в векторе оценок критериев при условии разной важности
критериев.
Критерий K1 является более важным, чем критерий K2 ( K1 K2 ). Исходная оценка
имеет вид K( x ) = ( 5,4,3,4 ) . Тогда оценка K 12 ( x ) = ( 4,5,3,4 ) . При этом полученная оценка не
является эквивалентной исходной оценке K( x ), т.к. рассматриваемые критерии не равны по
важности. Т.к. критерий K1 более важный, чем критерий K2 , то получаемая оценка ( 4,5,3,4 )
является худшей, чем исходная оценка ( 5,4,3,4 ) по значению первого (более важного
критерия). Таким образом, исходная оценка K( X ) = ( 5,4,3,4 ), оценка K 12 ( x ) = ( 4,5,3,4 ) . При
этом ( 5,4,3,4 )~( 4,5,3,4, ), т.к. K1 K2 , то ( 5,4,3,4 ) ( 4,5,3,4 ) .
Таким образом, с точки зрения качественной теории важности критериев возможны
следующие ситуации: Ki K j , K j Ki , Ki ~ K j , Ki и K j являются несравнимыми по
важности ( Ki K j ,K j Ki , Ki ~ K j ) .
Введем в рассмотрение обозначения: ~ij – отношение эквивалентности векторных
оценок, вторая из которых получена путем перестановки i-го и j-го элементов в первой; ij –
отношение предпочтения векторных оценок, вторая из оценок получена путем перестановки i-
го и j-го элементов в первой. Тогда в рассмотренных примерах ( 5,4,3,4 ) ~23 ( 5,3,4,4 ) и
( 5,4,3,4 ) 12 ( 4,5,3,4 ). Т.е. предпочтение векторных оценок вида ( 3,5,4,5 ) ( 3,5,3,5 ) – это
предпочтение, полученное в результате сравнения значений скалярных оценок критериев на
соответствующих позициях, а ( 3,5,5,4 ) 34 ( 3,5,4,5 ) - предпочтение первой векторной оценки
перед второй, полученной в результате перестановки скалярных оценок в 3-ей и 4-ой позициях
при условии разной важности критериев K3 и K4 ( K3 K4 ) , при этом по критерию K3 в
полученной оценке меньшее значение.
Дополнительной информацией
для определения предпочтений ЛПР с точки зрения
важности критериев, используемой для принятия решений, является информация о
предпочтительности (важности) критериев или их эквивалентности (безразличии при анализе
оценок для соответствующих критериев). Пример дополнительной информации о
предпочтениях ЛПР, используемой в рассуждениях выше, имеет вид:
Ω = { k1 k2 ,k2 ~ k3 ,k3 k4 } .
Таким образом, комбинируя отношения ij ,~ij и отношение для векторных оценок
(соответственно, решений), можно выполнить сравнение по предпочтению всех векторных
оценок с использованием информации
.
Тогда могут быть определены (сформированы) новые отношения , порождаемые
информацией о предпочтениях ЛПР с точки зрения важности критериев
. Обозначим
отношение предпочтения , формируемое для векторных оценок решений x с использованием
дополнительной информации
через
.
Пример использования качественной информации о важности критериев
при решении
двухкритериальной задачи. Вид информации{K1 K 2 }, даны две векторные
оценки K( x1 ) ( 5,3 ) , K( x2 ) ( 2,4 ) .
58
Т.к. векторные оценки не сравнимы между собой (т.е. (5,3) (2,4) и (2,4) (5,3) и
x1 x2 , x2 x1 ) тогда при отсутствии предпочтений ЛПР с точки зрения важности критериев
эффективное решение не может быть определено.
При учете информации
 { K1 K2 } о важности критериев в векторной оценке K( x1 )
( 5,3 ) выполнена перестановка скалярных оценок (в позициях 1 и 2, соответствующих
информации ). В результате
получена
модифицированная векторная
оценка
K
12
( x )

( 3,5 )
. Т.к. для критериев
K
1
и
K
2
выполняется K
1
K
2
, тогда для оценок
K( x )
1
1
и K 12 ( x1 ) выполняется K( x1 ) 12 K12 ( x1 ) (т.к. значение по первому критерию является
более важным, чем значении по второму), т.е. ( 5,3 ) 12 ( 3,5 ) . Полученная оценка K 12 ( x1 )
может быть соотнесена с оценкой K( x
2
) ,
при этом
(3,5) (2,4)
или K 12 ( x
) K( x ). В
1
2
итоге получены две пары отношений:
для
K( x ) ,
K 12 ( x ) и
K 12 ( x ) ,
K( x
2
) в виде:
1
1
1
(5,3)
12
(3,5)
и
(3,5) (2,4)
(либо
K( x
)
12
K12
( x )
и K 12 ( x ) K( x
2
)),
которые в
1
1
1
сокращенной
форме
могут
быть
записаны
в виде
последовательности
отношений:
(5,3) 12 (3,5) (2,4).
Т.к. через
обозначено отношение предпочтения, полученное с использованием
дополнительной
информации
о
важности
критериев,
тогда
(5,3)

(2,4),
K( x1 )

K( x2 ) .
Пример использования дополнительной информации
Ω о равной важности критериев
K1иK2
при выборе эффективного решения.
Вид информации
 { K1 ~ K2 } ,
вид векторных оценок K( x
1
)

( 5,3 ) ,
K( x
2
) ( 2,4 ) .
Тогда (5,3) (2,4) ,
(2,4) (5,3) ,
x
1
x
2
,
x
2
x
1
,
(5,3) ~ (2,4) (где ~ – отношение безразличия (не
сравнимости) двух векторных оценок и, соответственно, решений). Использование
информации
о
равной важности
критериев для
ЛПР
позволяет
на основе
оценки
K( x
)(5,3)
сформировать оценку
K 12 ( x )
в
виде:
K
12
( x
)(3,5).
При
этом
1
1
1
K( x
)~12 K12
( x
)
,
так как при этом K 12 ( x ) K( x
2
), то следовательно
K( x
)
K( x
2
) и
1
1
1
1
x
1

x
2
.
Вариант
(решение)
x*i , такой, для которого
не
существует решений
x
j
таких,
что
x
x*
называется не доминируемым (по отношению
), т.е.
x
| x
x
*
.
Таким
j
j
j
i
i
образом,
решение
x*i
является не доминируемым
по
отношению
,
т.е.
с
учетом
дополнительной информации о важности критериев. Тогда может быть сформировано
множество X
не доминируемых
решений:
X

{ x
i
|

x
j
,x
j
xi }
. Только среди
этих
решений может быть выбрано эффективное.
Алгоритм
формирования
множества
X содержит рассматриваемую
ниже
последовательность шагов:
1) сформировать первоначальный вид множества не доминируемых решений следующим
образом: X
 { xi | i 1,n }, где n - общее количество решений;
2) выполнить проверку условия доминирования решением
xi
решения xl (условие вида
k
ij

k
lj
для всех
j
и k
ij
'
k
lj
'
для одного
j' ), при этом l
;
1, n
если условие доминирования
решения xl решением xi выполняется,
то исключить xl
из множества не доминируемых
решений X
: X
 X
\ xl ;
59
3) шаг 2 повторить для каждого решения xi ( i = 1,n ), исключая из множества X
на каждом
шаге доминируемые решения xl ;
4) для решения xi в соответствии с информацией о важности критериев
, содержащей
отношение предпочтения для критериев K j K h , сформировать на основе векторной оценки
K( xi ) новую векторную оценку K jh( xi ) , получаемую в результате перестановок значений
скалярных критериев K j и K h (значения kij и kih );
5) проверить выполнение условия доминирования для векторных оценок K( xi ) и K jh( xi ) ,
если условие
K( x )
jh
K
jh
( x
)
выполняется,
тогда выполнить
проверку
условия
i
i
доминирования векторных оценок
K( x )
векторной оценкой
K jh( x )
(при этом проверка
l
i
где l
);
выполняется последовательно для каждого l-го
решения,
1, n
если
условия
доминирования
оценки
K( x )
оценкой
K jh( x )
выполняется (т.е.
K
jh
( x
) K( x
) и,
l
i
i
l
соответственно,
K( xi )

K( xl
) ),
то решение K( xl ) исключается из множества
X
как
доминируемое :
X
 X
\ xl ;
6) изменение индекса текущего рассматриваемого решения xi (переход к следующему
решению), доминирование которым остальных решений xl ( l i 1,n ) в соответствии с
отношением будет исследоваться (при учете текущей информации о важности критериев
K
j
K h ); если решение xi , для которого исследуется доминирование им остальных решений
xl
( l
), имеется в наличии (i n) , тогда выполнить переход к шагу 4;
i

1,n
7)
если для всех решений xi X
выполнена проверка доминирования ими (текущим
рассматриваемым решением xi ) других решений xl
( l
) в соответствии о текущей
i 1,n
информацией о важности критериев
K
j
K
h
,
то в
выполнить переход к следующей
информации о важности критериев (K
j
'
K
h'
) ,
если | X |1 и в
имеется информация о
важности критериев K j ' K h' , то выполняется переход к шагу 4;
8) если в
дополнительная информация о предпочтительности критериев (K j ' K h' )
отсутствует, то выполняется переход к информации об эквивалентности критериев K j ~ K h ;
9) в соответствии с информацией об одинаковой важности критериев K j и K h для некоторого
решения
xi
на основе его векторной оценки K( xi
) формируется новая векторная оценка
K jh( x ) , где
j и
h - позиции в векторе критериев,
являющихся одинаковыми по важности;
i
полученная оценка
K jh( x
) в силу равной важности критериев
K
j
и K
h
( K
j
~ K
h
) является
i
эквивалентной
исходной
оценке
K( xi )
(т.е.
проверять
условие
доминирования
K( x )
jh
K jh ( x
) не требуется, K( x
) ~ K
jh
( x ) );
i
i
i
i
K( xl )
( l
)
10) проверка выполнения условия доминирования
векторных
оценок
i

1,n
полученной
векторной оценкой K jh( x ) ;
если условие доминирования
оценки
K( x )
i
l
60
оценкой
K jh( x
) (условие
K jh ( x
) K( x ))
выполняется,
тогда
реализуется
i
i
l
K( x
i
)

K( x
l
)
(т.е.
доминирование
с учетом дополнительной информации о равной
важности
критериев);
тогда
решение
xl исключается из X
как
доминируемое
: X
 X
\ xl ;
11) изменение индекса рассматриваемого решения xi (переход к следующему решению), т.е.
выполняется переход к решению, доминирование которым остальных решений xl ( l i 1,n )
будет исследоваться (при учете дополнительной информации об одинаковой (равной)
важности
критериев
K
j
и
K h
( K
j
~ K
h ));
при
наличии
решения
xi
(условие i n ),
доминирование которым решений
xl
при учете
K
j
~ K
h
будет исследоваться,
выполняется
переход к шагу 9;
12) в случае, если проверка для всех
xi ( i
) условия доминирования ими решений
xl
1,n
( l
)
дополнительной информации K
j
~ K
h
)
i 1,n
(с
учетом текущей
рассматриваемой
выполнена, тогда при условии
| X |1
в
выделяется
информация,
касающаяся
эквивалентности других критериев ( K
j
'
~ K
h'
), индекс текущего рассматриваемого решения
задается равным 1( i1, рассматривается решение x1 ), выполняется переход к шагу 9.
Примечание. Необходимость исключения решений xl
из множества X
исследуется
первоначально с точки зрения разной важности критериев
K j
и K h
(предпочтений
для
критериев
K j
и K h
– K
j
K h ),
а затем с точки зрения одинаковой важности критериев
( K
j
~ K
h
).
Это
объясняется
тем,
что дополнительная информация
, используемая при
принятии решений, представляется в виде двух матриц – первая матрица A1
предпочтений для
1 если K j
K h и a jh
0, если
K
j
Kh , j
, h
),
А2
критериев (
a
jh
1, n
1, n
вторая матрица
«эквивалентных» критериев (критериев, имеющих одинаковую важность, K j ~ K h ).
Пример матрицы предпочтений критериев и матрицы отношения эквивалентности
критериев (с одинаковой (равной) важностью).
K1
А1 K2
K 3
K 4
K1K2 K3 K4
0 1 0 0
0 0 0 0
0 0 0 1
0 0 0 0
K1
; А2 K2
K 3
K 4
K1
K
2
K
3
K
4
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
.
Пример применения алгоритма многокритериального поиска эффективных
решений при учете важности критериев для задачи ранжирования студентов.
Информация о важности критериев имеет следующий вид:
Ω = { K1 K 2 , K 2 K3 , K3 K4 } . Векторные оценки K( xi ) для каждого решения xi
приведены
в Таблице 1. Рассматривается решение x1 . Т.к.
K
3
K
4
, то на основе векторной оценки
K( x1 ) = ( 3,5,5,4 )
может быть
сформирована
модифицированная векторная оценка
K
34
= ( 3,5,4,5 )
. Однако оценка
K( x
1
)
=
( 3,5,5,4 )
предпочтительной оценки
K
34
( x
1
) = ( 3,5,4,5 )
в
силу важности:
критериев (
K( x
1
)
34
K
34
( x
1
)
или (3,5,5,4)
34
(3,5,4,5) ).
Сравниваем
6
1
векторную оценку
K 34
(3,5,4,5)
с векторной
оценкой
K( x
4
)
=
( 3,5,3,5 )
с
точки
зрения
выполнения условия k1 j
k
4
j
для всех
k
i j
(
i =
1,4
)
и для одного
k
13
>
k
43
.
Т.к. эти условия
выполняются, то x4

X
, при этом т.к.
x
4
~
x
6
, то x6 X
. Таким образом:
( 3,5,5,4 )
34
( 3,5,4,5 )
Ω
( 3,5,3,5 )
;
K( x
1
)
34
K
34
( x
1
)
Ω
K( x
4
)
~
K( x
) .
6
Для решения
x
1
выполним модификацию его векторной оценки
K( x
1
)
следующим
образом:
K( x
1
)
=
( 3,5,5,4 )
,
K
12
( x
1
) = ( 5,3,5,4 )
.
Если бы оценка
K( x
)
доминировала оценку
1
K
12
( x
) ,
тогда при
K 12
( x
)
K( x )
имели:
K( x
)
K( x
) ,
но т.к. K( x
)
Ω
K
12 ( x
), то
1
1
Ω
Ω
1
1
7
1
7
K( x
1
)
Ω K( x7 ) , следовательно,
решение x7
не может быть исключено из множества
X Ω .
Рассмотренным действием была учтена важность критериев
вида
K1 K2
в
.
Проинтерпретируем информацию об одинаковой важности K 2 и K3 в
. Для K1 и K 2
изменение позиций оценок k
12
, k
13
и k
22
, k
23
не имеет смысла т.к. оценки
K( x
1
)
и
K( x
2
)
при
этом не изменяются,
x
4
, x
5
, x
6
исключены из рассмотрения,
поэтому информация
K2~K3
может быть применена только к решениям x3 и x7 . Для решения x3
на основе его векторной
оценки
K( x3 )
при
учете
(
K
2
~ K
3
) может
быть
сформирована новая
векторная
оценка
K
23
( x
3
) = ( 5,3,4,3 )
, т.к.
K
2
~ K
3
,
то
K( x
3
)
~
K
23
( x
3
) . Сравнение K 23 ( x
3
) с
K( x )
показывает,
7
что
K
23
( x
3
)
~
K( x
)
.
Тогда
может
быть
сформирована
следующая
цепочка:
7
K( x
3
)
~
K
23
( x
3
)
~
K( x
)
,
поэтому
в итоге
K( x
3
)
~
K( x
)
и
x
3
~
x
7
.
Поэтому
множество
7
7
недоминируемых решений X Ω ,
сформированное с учетом информации о различной и
одинаковой важности критериев, будет иметь вид:
X
Ω
=
{ x
1
, x
2
, x
3
, x
7
}
.
2.3. Использование количественной теории важности критериев при принятии
решений
При использовании количественной теории важности критериев для принятии решений
используются следующие формы задания их (критериев) важности:
1) cтепень превосходства в важности одних критериев над другими (критерий K i в h раз
важнее критерия K j ), степень превышения важности критерия K i относительно критерия K j
обозначается через h , где h 0 , понятно, что при h1 критерий K i в h раз важнее критерия K
j , при h1 (для K i K j ) критерий K j в 1/ h1 раз важнее критерия K i , при h1 критерии K i и
K j равно важны (эквивалентны по важности, т.е. K i ~ K j );
2) задание абсолютного значения важности критериев, количественно измеряемой по общей
шкале важности, в этом случае важность критерия K i имеет величину
i ,
i 0 .
Первый способ задания важности критериев связан со вторым способом с помощью
следующей формулы: h
i /
j , где h - степень превосходства важности
i критерия K i
над важностью
j критерия K j .
Утверждение о степени превосходства важности критерия K i над важностью критерия K
j в h раз обозначается следующим образом: K i h K j . Для обозначения количественной
информации о степенях превосходства важностей критериев K i введен в рассмотрение
символ (т.е. – информация о важности критериев, характеризующая предпочтения ЛПР).
Для использования количественной информации о важности критериев выполняется
расширение исходной модели «качественной» важности критериев до так называемой N -
62
кратной модели ( N -модели). Способ построения N -модели может быть рассмотрен на основе
примера, введенного в рассмотрение выше (определение студентов, наиболее
предпочтительных с точки зрения успеваемости).
Для упомянутого примера качественная информация о важности критериев
K1, K2 , K3, K4 имеет вид: {K1 K2 , K2 ~ K3, K3 K4}. Допустим, что на основе
качественной информации получена количественная информация в следующем виде:
{K1 3/2 K2,K2~K3,K3 2 K4 }.
С точки зрения изучаемых дисциплин, каждой из которых соответствует свой критерий
K i , введенную в рассмотрение дополнительную информацию о важности критериев можно
прокомментировать следующим образом. Предмет 3 (критерий K 3 ) состоит из двух разделов,
каждый из которых эквивалентен предмету 4 (критерий K 4 ). Т.к. предмет 3 содержит два
раздела, а предмет 4 один раздел, то K3 2 K4 . Предмет 1 (критерий K1 ) состоит из трех
разделов, каждый из которых имеет одинаковую важность с одним из двух разделов второго
предмета (критерий K 2 ), поэтому K1 3 / 2 K 2 . Рассмотрим для принятия решений на основе
качественной информации о важности критериев полученное в предыдущем разделе
множество X . Расширенная модель принятия решений введена в следующем виде:
1) Исходное множество решений X , для которого формируется расширенная N -модель
имеет вид X Ω = { x1 , x2 , x3 , x7 } ;
2) для каждого решения xi ( i{1,2,3,7}) его векторная оценка формируется путем повторения
скалярной оценки kij (где i – индекс решения, j – индекс критерия) такое количество раз,
сколько равноважных разделов содержит соответствующий j-ый предмет;
3) сформированная расширенная модель с учетом количественной важности критериев
примет в этом случае следующий вид (формируются новые векторные оценки):
K
( x ) ( 3,3,3,
5,5,
5,5,
4
)
;
1
1ый
2ый
3ый
4ый
предмет
предмет
предмет
предмет
K
( x
2
)

(
4,4,4,
4,4,
4,4,
5
)
;
1ый
2ый
3ый
4ый
предмет
предмет
предмет
предмет
K
( x
3
)

(
5,5,5,
4,4,
3,3,
3
) ;
1ый
2ый
3ый
4ый
предмет
предмет
предмет
предмет
K
( x
4
)

(
5,5,5,
3,3,
4,4,
3
) .
1ый
2ый
3ый
4ый
предмет
предмет
предмет
предмет
Полученные векторные оценки K
( xi ) могут быть проинтерпретирована как состоящие
из восьми критериев c одинаковой важностью. Число повторений для критериев K i
определяется на основе значений
i , соответствующих этим критериям: для критерия K1 :
n1 3 ; для K 2 : n2 2 ; для K 3 : n3 2 ; для K4 : n41. Тогда N -модель представляет собой
совокупность количества повторений скалярных оценок для каждого критерия, т.е. N -модель
63
представляет собой вектор
N (n
1
, n
2
,..., n
m
) , где
m -
количество
критериев, который
содержит количество повторений скалярных оценок
k ij каждого из критериев K j . Таким
образом, N -модель – это модель с
n
1
n
2
...

n
m
скалярными оценками, где первые n1
оценок – это повторение n1
раз оценки ki1 в исходном векторе K j , вторые n2
оценок – это
повторение n2 раз
оценки
ki 2 в исходном векторе K j
и т.д. Если
N -модель в виде
N (n1 , n2 ,..., nm )
сформирована,
то отдельный
коэффициент
i
в
аддитивной
многокритериальной модели (аддитивная свертка)
может быть определен
следующим
m
образом:
i ni /ni .
i 1
Таким образом N - модель – это совокупность чисел ni , каждое из которых определяет
число повторений скалярной оценки kij из исходной векторной оценки в формируемом новом
векторе значений.
Определение. Критерий K i в h раз важнее критерия K j , если на основе N -модели
коэффициент важности h может быть определен следующим образом: ni / n j h . При этом
каждая из ni оценок критерия K i в формируемом векторе K
( xl ) имеет равную важность с
любой из n j оценок критерия K j в этом же векторе.
В соответствии с сформированным определением и введенным выше выражением вида
h
i /
j приходим к выводу, что h ni / n j
i /
j , где
i и
j - коэффициенты важности
критериев.
Владея информацией о значениях
i и
j
может быть выполнен переход к
значениям ni и n j , формирование N -модели и ее использование для принятия решений.
важности критериев
i (i
)
Один
из способов определения коэффициентов
1, m
предполагает из попарное сравнение по абсолютной важности. В ходе использования данного
метода строится матрица A (aij ) mm парных сравнений критериев K1 ,..., K m по важности.
ЛПР указывает свои предпочтения относительно важности критериев следующим образом:
aij1 если K i
K j и
aij 0 , если K i K j . Тогда важность i-го критерия
K
i
(выраженная
m
коэффициентомх
i ),
определяется формулой
i ai / m ( ai 0 ), где
a
i


a
ij
. Если
j1
значения
i являются дробными (если дробная часть
i не равна 0), а значения n i должно быть
строго целым, то для приведения
i к требуемому виду их необходимо умножить на
соответствующее натуральное число. Рассмотрим пример для двух критериев.
Пример приведения дробных значений коэффициентов важности
о к целому виду :
1)
i
0,2
;
j
0,4
,
следовательно, коэффициенты должны быть умножены на 10, тогда
ni
2 ;
n j
4 ;
2)
i 0,25 ;
j 0,45 , следовательно, коэффициенты должны быть умножены на 100, тогда
n
i

25
; n
j
45;
Таким
образом, если получены значения
n
1
, n
2
,..., n
m
,
то N -модель может быть
представлена в следующем виде: N (n1 , n2 ,.., nm ) . Например,
если n1 2 , а n2 4 то N -
модель имеет вид N (2,4) .
Пример построения ni -оценок для соответствующих N -моделей.
1) если m 2 , исходная векторная оценка K( xi ) имеет вид (2,5) , а N -модель имеет вид
(3,4) , тогда K
( xi ) - оценка будет представлена в виде K
( xi ) ( 2,2,2,5,5,5,5 ) ;
64
2) если m 2 , исходная векторная оценка K( xi ) имеет вид (3,6) , а N - модель имеет вид
(3,5) , тогда K
( x ) - оценка будет представлена в виде
K
( x
) ( 3,3,3,6,6,6,6,6 ) .
i
i
В
силу
того, что в
построенной N - модели
(соответственно, в
оценках K
( x )
i
( i
1,m
))
все
критерии
являются одинаково важными,
тогда для
определения не
доминируемых решений (решений xi X
, где X
- множество не доминируемых решений,
сформированное на основе количественной информации
о важности критериев)
используются введенные выше условия вида: k k и k k хотя бы для одной оценки
ij il ij' il'
kij ' . Таким образом, формирование N-модели должно обеспечивает приведение всех критериев к
одинаковой степени важности (все оценки в K
( xi ) являются равными по важности). Для
удобства выполнения действий по сравнению оценок kij
вектора K эти оценки могут быть
предварительно упорядочены по убыванию. Таким образом, выполняется сравнение
непосредственное сравнение оценок kij
для соответствующих решений, устанавливается
отношение предпочтения (доминирования) между оценками K
( xi ) и K
( xl ) , и,
соответственно, между самими решениями (т.е. xi xl ).
Пример выбора недоминируемых решений x*i X
на основе множества X
,
полученного путем анализа качественной информации о важности критериев.
В процессе решения рассматриваются альтернативы X 1 , X 2 , X 3 , X 7 . Оценки K( xi )
для них приведены в Таблице 1. Информация
о степенях важности критериев имеет вид:
{K
1
3/2 K
2
, K
2
~ K
3
, K
3
2 K
4
}
,
т.е. N -модель, имеет вид:
N (3,2,2,1) . Оценки K
( x )
i
в
соответствии
с
N
-
модели
следующие:
K
( x ) ( 3,3,3,5,5,5,5,4 ) ;
1
K
( x
2
)

( 4,4,4,4,4,4,4,5 )
;
K
( x
3
) ( 5,5,5,4,4,3,3,3 ) ;
K
( x ) ( 5,5,5,3,3,4,4,3 ) .Для
7
удобства дальнейших действий полученные оценок отсортированы по убыванию. В итоге:
K
( x1 ) ( 5,5,5,5,4,3,3,3 ) ; K
( x2 ) ( 5,4,4,4,4,4,4,4 ); K
( x3 ) K
( x7 ) ( 5,5,5,4,4,3,3,3 ) .
С точки зрения введенных условий для недоминирования (предпочтения) и
доминирования решений имеем: K
( x1 ) K
( x3 ) , K
( x1 ) K
( x7 ). Т.е. решения x3 и
x7
не
могут
быть
включены
в множество
недоминируемых
решений X
(т.е.
X
X
\ { x
3
, x
}
).
Сравнение
оценок
K
( x )
и
K
( x
2
)
показывает,
что
7
1
K
( x )
K
( x
)
и
K
( x
)
K
( x ) , т.е.
оценки
K
( x
)
и
K
( x
)
являются
2
2
2
1
1
1
несравнимыми с использованием отношения . В итоге имеем
x
x
3
,
x
x
,
x
1
x
2
,
1
1
7
x
2

x
1
,
где
–
отношение
предпочтения,
формулируемое
с
учетом
количественной
информации
о важности критериев.
Понятно, что приведенный подход может быть применен непосредственно к множеству
решений X без выделения множества X
недоминируемых решений с использованием
качественной информации о важности критериев.
2.4. Использование теории относительной важности критериев при принятии
решений
При реализации выбора эффективных решений (в частности, в случае двух критериев)
возможными стратегиями, которыми руководствуется ЛПР, являются: 1) стратегия
компенсации; 2) стратегия исключения.
65
Стратегия компенсации предполагает, что незначительное уменьшение значения по
одному из критериев компенсируется более значительным увеличением второго критерия.
Стратегия исключения предполагает удаление из рассмотрения решения, которые не
удовлетворяют введенным в рассмотрение ограничивающим условиям. По аналогии с
рассмотренным ранее подходом теории важности критериев принятые обозначения имеют
вид: K (K1 , K 2 ,..., K m ) - векторный критерий, Х - множество возможных решений,
( xi x j ) – отношение предпочтения, заданное на множестве векторных оценок K( xi ) .
Понятно, что K( xi ) K( x j ) ( xi x j ) .
В основе теории относительной важности критериев положено следующее определение
уступки и приращения для рассматриваемых критериев (в нашем случае, m 2 ). Пусть i и j
- два различных номера критериев. Тогда критерий K i важнее критерия K j с заданными
положительными параметрами wi и w j , если для двух векторов K( xl ) и K ( xh ) вида:
K( xl ) ( K1( xl ),K 2 ( xl ),.., Ki ( xl ),.., K j ( xl ),.., K m ( xl )) ,
K( xh ) ( K1( xh ),K 2 ( xh ),.., Ki ( xh ),.., K j ( xh ),.., K m ( xh ))
имеет место
K( xh ) K( xl ) , при этом
k
h,i

k
l ,i
w
i
; k
h, j
k
l , j
w
j
и
k
hs

k
ls
при
s1,2,...,m и s i , s j .
В силу введенного в рассмотрение определения векторы
K( xl )
и K ( xh ) отличаются
только i-ой и j-ой компонентами (т.е. значениями k
h,i
, k
h , j
, k
l ,i
,
kl , j ).
Таким образом, в соответствии с введенными определением K( xh ) K( xl
) , тогда ЛПР
может выполнить уступки w j по критерию
K j , для того, что получить приращение wi по
критерию K
i
( k
h,i

k
l ,i
на величину
w
i
, а k
h , j

k
l , j
на величину w
j
). Т.е. если для критерия
K j может быть выполнения уступка w j для получения приращения wi
критерия K i
(а в
результате решение xh предпочтительнее решения xl ), то критерий K i является более
важным, чем критерий K j . Т.к. в результате xh xl , то K i K j .
Степень важности критерия K i по сравнению с критерием K j
определяется как wi / w j .
Для того, чтобы важность критерия K i по сравнению с критерием
K
j
была пронормирована,
должен быть использован коэффициент относительной важности критерия K i , вычисляемый
следующим образом:
ij
w j
.
w
i
w j
Если
ij
1 , то за небольшое приращение
w
i
критерия
K
i
должна быть реализована
значительная уступка w
j
по критерию K
j
(т.е. w
i

w
j
). В этом случае критерий K
i
имеет
высокую степень важности по сравнению с критерием
K j . Если
ij
0 , то потери
w
j
по
критерию
K j
должны обеспечивать значительное приращение
wi
по критерию
K
i
. В этом
случае критерий
K j является более важным, чем критерий
K
i
и
wi
w
j
. Если
wi w
j
, то
ij

1 / 2 .
Таким образом, определение относительной
важности
критериев
K i
и
K j
реализуется путем задания значений уступок w j
и приращений
w
i
для соответствующих
критериев
K
j
и
K i . Использование относительной
важности
критериев (коэффициента
66
относительной важности
ij ) в процедуре принятия решений для выявления эффективных
альтернатив основывается на понятии инвариантности отношения предпочтения.
Бинарное отношение R , заданное на пространстве R m , называется инвариантным
относительно линейного положительного преобразования, если для произвольных двух
векторов K( xl ) и
K ( xh )
из
выражения K( xl ) K( xh ) следует соответствие
(

K( xl ) C ) (

K( xh ) C ) ,
где C
- задаваемый вектор значений,
- положительный
коэффициент (
 0) .
Для задач многокритериального выбора отношение предпочтения
может считаться инвариантным относительно линейного положительного преобразования. Из
свойств инвариантности отношения вытекают свойства аддитивности и однородности этого
отношения, т.е.:
из K( xl
) K( xh ) ( K( xl ) C ) ( K( xh ) C ) ;
из
K( xl ) K( xh )
K( xl )

K( xh ) .
Т.е. к
векторам значений критериев K( xl )
и
K ( xh ) может быть
прибавлен вектор
C и при этом отношение предпочтения не изменится. Вектора K( xl ) и
K ( xh ) могут быть умножены на положительное число
и
при этом отношение
предпочтения также не изменится.
2.5. Использование понятия относительной важности критериев для сужения
множества эффективных решений в многокритериальной задаче
Рассмотрение механизма использования относительной важности критериев для сужения
множества выбираемых (эффективных) решений предварим формулировками аксиом ЛПР,
которыми он руководствуется в процессе выбора. Для вводимых в рассмотрение аксиом
определим следующие обозначения: C( X ) – множество эффективных (выбираемых) решений,
C(K ) – множество соответствующих этим решениям векторов значений критериев.
Аксиома 1. Для всякой пары
векторов
K( xl )
и
K ( xh ) , для которых
имеет место
K( xl
)
K( xh ) , выполняется
K( xh
)
С(K)
.
Аналогично, для всякой
пары
допустимых
решений xl и xh , для которых имеет место соотношение xl xh , выполняется xhC( X ) .
Аксиома 2. Иррефлексивное отношение предпочтения , которым ЛПР руководствуется в
процессе выбора, является транзитивным бинарным отношением.
Аксиома 3. Каждый из критериев K1 , K 2 ,..., K m согласован с отношением предпочтения
(при прочих равных значениях критериев K j
( j
) сравнение решений может быть
1,m
выполнено с использованием одного критерия K i
(при i j )); данное свойство выполняется
для каждого критерия.
Тогда при условии, что для задачи многокритериального принятия решений
выполняются аксиомы 1-3 и условие инвариантности отношения , при условии большей
важности критерия K i по сравнению с критерием K j на основе множества С( X ) и множества
C(K ) (выбираемых решений и выбираемых критериев) могут быть сформулированы новые
множества С' (X ) и C' (K) , где множество С' (X ) является сужением исходного множества
С (X ) , а множество векторов C' (K) определяется в соответствии с изложенной ниже
процедурой.
Если критерий K i является более важным, чем критерий K j с параметрами wi и w j , то
модифицированная оценка K'j менее важного критерия может быть определена следующим
образом:
K 'j w j K i wi K j ,
K s' K s , при s1,2,..., m и s j .
В результате для некоторого решения xh формируется вектор модифицированных значений
критериев K' ( xh ) ( K1'( xh ),K2' ( xh ),..,K'j ( xh ),..,Km' ( xh )) . В результате на основе
67
полученных модифицированных векторов K' ( xh ) критериев K's ( xh ) ( s 1,m ) для решений
xhC( X ) должна быть выполнена проверка выполнения отношения строгого предпочтения.
Те решения xh ,
для которых выполняется условие
xl xh
(при
K' ( xl ) K' ( xh ) ),
в
множество С' ( X ) включены быть не могут. Тем самым количество элементов в С' ( X ) может
быть уменьшено
(т.е. | С'(X ) || С(X ) |). Для
введенного в рассмотрение выражения,
с
использованием которого вычисляется
оценка
K'j , могут быть выполнены следующие
преобразования.
Вследствие
инвариантности
отношения(и множества С( X )
соответственно) правую часть выражения для критерия K'j разделим на wi
w j , оставив для
K ' тоже обозначение. Получим K'

ij
K
i
(1
ij
)K
j
, где критерий K
i
более важен, чем
j
j
критерий K
j
,

ij
- коэффициент важности критерия. В дальнейшем с целью сужения
множества С(X )
при получении
векторных оценок
K' ( xh )
должна
быть использована
полученная формула.
Таким образом, «новый» векторный критерий K'
получен из «старого» критерия
K
заменой менее важного скалярного критерия K j
на линейную комбинацию критериев K i
и
K j с коэффициентами wi и w j
(коэффициентом
ij ). Все остальные скалярные критерии K s
сохраняются (при s1,2,..., m и s j ).
Пример сужения множества выбираемых решений С(Х) на основе относительной
важности критериев с коэффициентами wi и w j .
Заданными являются значения коэффициентов w1 и w2 : w1 = 1 ; w2 = 2 . Т.е. уступка по
критерию K1
в одну единицу должно обеспечивать приращение по критерию
K
2
в две
единицы (критерий K1
является более важным, чем критерий
K2 ).
Тогда
ij
0.67 ,
а
(1ij ) 0.33 .
Исходное
множество
решений
Х имеет вид:
X = { x
, x
2
, x
, x
, x , x
, x
}
,
1
3
4
5
6
7
значения критериев
K
i
(
i =
1,4
) для соответствующих значений сведены в Таблицу 2.
Таблица 2. Значения критериев K i
( i =
1,4
) для решений xl
( l =
1,
)
K i
K1
K
2
K
3
K
4
xl
x1
3
5
5
4
x2
5
4
3
5
x3
5
4
4
3
x4
2
5
3
3
x5
4
2
4
5
x6
3
5
3
2
x7
4
5
3
5
Решение
x5 доминируется решением x7 ( x7
x5 ), поэтому
x5C( X ) , решение x6
доминируется
решением x1 , поэтому
x6C( X )
при x1 x6 .
Решения
x1 , x2 , x3 , x4 , x7
являются не сравнимыми между собой,
поэтому
C( X )

{ x1 , x2 , x3 , x4 , x7 }
. Значения
K' ( x
l
)
определены в соответствии с введенной в рассмотрение формулой и сведены в Таблицу 3. Из
анализа значений K i′( i = 1,4 ) видно, что x2 x7 , x3 x4 , поэтому сформированное множество
C′(X ) будет иметь вид: C′(X ) = { x1 , x2 , x3 } . Решения, входящие в это множество, являются
эффективными.
68
Таблица 3. Значения критериев
K
i
′
(
i = 1,4
) для решений
x
l
( l = 1, )
K i
K
1
K
2
K
3
K
4
xl
x1
3
3.66
5
4
x2
5
4.67
3
5
x3
5
4.67
4
3
x4
2
2.99
3
5
x7
4
4.33
3
5
Из анализа значений K i′( i = 1,4 ) видно, что x2 x7 , x3 x4 , поэтому сформированное
множество C′(X ) будет иметь вид: C′(X ) = { x1 , x2 , x3 } . Решения, входящие в это
множество, являются эффективными.
3. Программа выполнения работы
Для первого варианта задания предусматривается следующий порядок действий по
выполнению лабораторной работы:
1) на основе информации Ω о качественной важности критериев сформировать матрицы А1 и
А2 отношений предпочтения и эквивалентности для критериев K i ( i = 1,n );
2) разработать процедуру определения доминируемых решений, выполняющую для каждого
решения xl сравнение его значений скалярных оценок kl i вектора K (xl ) с такими же
скалярными оценками khi решений xh ; тем самым должны быть определены решения xh ,
доминируемые текущим рассматриваемым решением xl (при h = 1,n и h ≠l ); результатом
выполнения процедуры является множество X Ω не сравнимых между собой с использованием
отношения предпочтения решений;
3) разработать процедуру, использующую информацию Ω о важности критериев, входными
данными для которой будет являться матрица А1 отношения предпочтения для критериев;
разрабатываемая процедура должна выполнять следующие операции:
а) для решений xl (при l = 1,n ) формировать новые векторные оценки K ji (xl ) путем перестановки
скалярных компонент kli и k l j в исходной векторной оценке K (xl ) (индексы i и j
соответствуют критериям K i и K j , связанным отношением предпочтения в следующем виде:
Ki
K j
);
б)
для
каждого
решения
x
l
для его модифицированных векторных оценок
K
ji
(
x
l
)
проконтролировать
выполнение
условия
доминирования им других решений xh
для их
векторных оценок
K
ji
(
x
h
)
(при
и h ≠l ) (т.е. выполняется поэлементное сравнение
h = 1,n
оценок kli и khi из соответствующих векторов K ji (xl ) и K ji (xh )); при выполнении условия xl
xh , процедура реализует исключение решения xh из множества X Ω : X
 X
\ xh ;
в) результатом выполнения разрабатываемой программы является определение множества не
сравнимых решений X Ω , сформированного на основе информации Ω о предпочтениях
критериев вида Ki K j ;
4) разработать процедуру, использующую информацию Ω о важности критериев, входными
данными для которой будет являться матрица А2 отношения эквивалентности для критериев;
разрабатываемая процедура должна выполнять следующие операции:
а) для решений xl (при l = 1,n ) формировать новые векторные оценки K ji (xl ) путем перестановки
скалярных компонент kli и k l j в исходной векторной оценке K (xl ) (индексы i и j
69
соответствуют критериям K i и K j , связанным отношением эквивалентности в следующем
виде: K i K j );
б) для модифицированных векторных оценок K ji (xl ) каждого решения xl (при l = 1,n )
проконтролировать выполнение условия доминирования им других решений xh для их
векторных оценок K ji (xh ) (при h = 1,n и h ≠l ) (т.е. выполняется поэлементное сравнение
оценок kli и khi из соответствующих векторов K ji (xl ) и K ji (xh )); при выполнении условия xl
xh , процедура реализует исключение решения xh из множества X Ω : X
 X
\ xh ;
в) результатом выполнения разрабатываемой программы является определение множества не
сравнимых решений X Ω , сформированного на основе информации Ω об эквивалентности
критериев вида K i K j ;
5) выполнить вывод множества X Ω , полученного в результате исключения из него
доминируемых решений xh при учете дополнительной информации Ω о предпочтениях и
эквивалентности критериев.
Для второго варианта задания предусматривается следующий порядок действий по
выполнению лабораторной работы:
1) на основе информации Θ о количественной важности критериев сформировать N-модель в
виде вектора, каждый i-ый элемент которого соответствует i-му критерию и определяет число
повторений исходных скалярных оценок kli в формируемом векторе K Θ (xl ) (при l = 1,n );
2) разработать процедуру определения доминируемых решений, выполняющую для каждого
решения xl сравнение его значений скалярных оценок kl i вектора K (xl ) с такими же
скалярными оценками khi решений xh ; тем самым должны быть определены решения xh ,
доминируемые текущим рассматриваемым решением xl (при h = 1,n и h ≠l ); результатом
выполнения процедуры является множество X Θ не сравнимых между собой с использованием
отношения предпочтения решений;
3) разработать процедуру, использующую информацию Θ о важности критериев, входными
данными для которой будет являться сформированный вектор значений, интерпретируемый как N-
модель; разрабатываемая процедура реализует формирование векторов K Θ (xl ) ( l = 1,n ),
представляющих собой модификацию исходных векторных оценок K (xl ) ( l = 1,n ) по
соответствующему виду N-модели; таким образом, результатом реализации процедуры
являются модифицированные с учетом информации Θ о количественной важности критериев
векторные оценки K Θ (xl ) ( l = 1,n );
4) разработать процедуру, упорядочивающую по убыванию скалярные оценки kli ( i = 1,n ) для
каждой сформированной векторной оценки K Θ (xl ) ( l = 1,n );
5) для модифицированных векторных оценок K Θ (xl ) каждого решения xl ( l = 1,n )
проконтролировать выполнение условия доминирования им других решений xh для их
векторных оценок K Θ (xh ) (при h = 1,n и h ≠l ) (т.е. выполняется поэлементное сравнение
оценок kli и khi из соответствующих векторов K Θ (xl ) и K Θ (xh )); при выполнении условия xl
xh , процедура реализует исключение решения xh из множества X Θ : X
 X
\ xh ;
6) результатом выполнения разрабатываемой программы является определение множества не
сравнимых решений X Θ , сформированного на основе информации Θ о количественной
важности критериев;
7) выполнить вывод множества X Θ , полученного в результате исключения из него
доминируемых решений xh при учете дополнительной информации Θ о количественной
важности критериев.
Для третьего варианта задания предусматривается следующий порядок действий по
выполнению лабораторной работы:
70
1) на основе задаваемых в качестве входных данных значений wi и w j , соответствующих
уступкам и приращениям для критериев K i и K j , вычислить значения коэффициентов
относительной важности критериев Θij ;
2) разработать процедуру определения доминируемых решений, выполняющую для каждого
решения xl сравнение его значений скалярных оценок kl i вектора K (xl ) с такими же
скалярными оценками khi решений xh ( h = 1,n и h ≠l ); тем самым должны быть определены
решения xh , доминируемые текущим рассматриваемым решением xl (при h = 1,n и h ≠l );
результатом выполнения процедуры является множество X ′ не сравнимых между собой с
Θ
использованием отношения предпочтения решений;
3) разработать процедуру определения значений векторных оценок K ′(xl ) для всех n решений ( l
= 1,n ) c учетом вычисленных значений Θij ; при этом учесть, что при wi < w j критерий является
менее важным, чем критерий K i ; в этом случае пересчитываются скалярные оценки kl j ,
соответствующие этому j-му критерию (в этом случае определяется скалярная оценка
k
l′j, входящая в модифицируемый вектор K ′(xl ));
4) для модифицированных векторных оценок K ′(xl ) каждого решения xl ( l = 1,n )
проконтролировать выполнение условия доминирования им других решений xh для их
векторных оценок K ′(xh ) (при h = 1,n и h ≠l ) (т.е. выполняется поэлементное сравнение
оценок kli и khi из соответствующих векторов K ′(xl ) и K ′(xh )); при выполнении условия
x
l
x
h
, процедура реализует исключение решения
x
h
из множества
X
′
:
X
X
\ x
h
;
Θ
5) результатом выполнения разрабатываемой программы является определение множества не
сравнимых решений X Θ ,
сформированного
на основе
информации об относительно й
′
важности критериев;
множества X Θ , полученного в
результате
исключения из
него
7) выполнить вывод
′
доминируемых решений xh
при учете информации об относительной важности критериев.
4.Задание на работу
В качестве исходных данных для выполнения задания по лабораторной работе (для всех
вариантов) заданы: множество решений вида
X = { x
1
, x
2
, x
3
, x
4
, x
5
, x
6
, x
7
, x
8
}
, оценки
пяти
критериев сведены в Таблицу 4.
Таблица 4. Скалярные оценки ki j критериев K j для решений xi
(
i =
1,8
, j =
1,5
)
Варианты
Критерии
K
1
K 2
K 3
K 4
K
5
x1
3
5
5
4
4
x2
4
4
4
5
4
x3
5
4
3
3
5
x4
3
5
3
5
3
x5
4
2
4
5
5
x6
3
5
3
5
3
x7
5
3
4
3
4
x8
4
5
3
4
3
Вариант 1. Определить множество несравнимых решений X Ω , используя качественную
информацию о важности критериев Ω в следующем виде:
71
Ω ={K1 K2,K2 K3,K3 K4 ,K4 K5 }.
Вариант 2. Определить множество несравнимых решений X Θ , используя
количественную информацию о важности критериев Θ в следующем виде:
Θ ={K3 3 K4,K1 2 K4,K4 2 K2,K2K5 }.
Вариант 3. Определить множество несравнимых решений C′(X ) , используя
информацию об относительной важности критериев в следующем виде:
w1 = 2 , w2 = 1 ;
w4 = 1 , w5 = 2 .
5. Контрольные вопросы.
5.1. В каких ситуациях возникает необходимость учета важности критериев?
5.2. В чем состоят условия доминирования векторной оценки со стороны другой векторной
оценки (одного решения другим решением при наличии векторного критерия) ?
5.3. В чем заключается понятие качественной важности критериев?
5.4. В какой форме может быть задана информация о качественной важности критериев?
5.5. В чем состоит способ формирования модифицированных векторных оценок решений на
основе исходных векторных оценок с учетом качественной информации?
5.6. В чем заключаются условия доминирования сформированной модифицированной
векторной оценкой исходной векторной оценки при учете качественной информации о
важности критериев для одного и того же решения (в каком случае модифицированная
векторная оценка доминирует исходную векторную оценку) ?
5.7. В какой ситуации сформированная модифицированная векторная оценка не доминирует
исходную векторную оценку?
5.8. В чем состоят условия доминирования векторной оценкой одного решения векторной
оценки другого решения при учете качественной информации о важности критериев?
5.9. В чем причина доминирования сформированной векторной оценкой исходной векторной
оценки при условии эквивалентности критериев?
5.10. Какие шаги формируют алгоритм определения состава множества X Ω не сравнимых
решений при учете информации Ω о качественной важности критериев?
5.11. Что представляет из себя понятие количественной важности критериев?
5.12. Как определить относительную важность критерия K i по сравнению с критерием K j ,
если важность K i равна βi , а важность K j равна β j ?
5.13. В чем заключается способ построения N-модели с учетом количественной информации
Θ о важности критериев?
5.14. В чем заключается способ формирования модифицированных векторных оценок K Θ (xl
) на основе исходных оценок K (xl ) с учетом N-модели?
5.15. Каким образом можно выполнить переход от значений ni в N-модели к значениям
коэффициентов ai в аддитивной свертке значений всех критериев K i ( i = 1,m ) для решения xl ?
5.16. Как определяется коэффициент важности критерия K i по сравнению с критерием K j на
основе N-модели?
5.17. В чем состоит суть метода определения множества несравнимых решений X Θ (в чем
заключается алгоритм формирования множества X Θ )?
5.18. Как в теории относительной важности критериев задается преобладание важности
критерия K i по сравнению с критерием K j ?
5.19. В чем заключается понятие уступки и приращения и как они характеризуют
относительную важность критериев?
72
5.20. Каким образом вычисляется коэффициент относительной важности критерия K i (по
сравнению с критерием K j ) и как значение этого коэффициента характеризует относительную
важность критериев K i и K j ?
5.21. Каким образом формулируются аксиомы принятия решений при многих критериях
5.22. В чем заключается способ модификации исходных векторных оценок K (xl ) для
получения оценок Kxl?
5.23. Каким образом выполняется сужение множества несравнимых решений с
использованием информации об относительной важности критериев (какова
последовательность шагов алгоритма сужения множества несравнимых решений с
использованием информации об относительной важности критериев)?
73
ЛАБОРАТОРНАЯ РАБОТА №6
ИССЛЕДОВАНИЕ ПРИМЕНЕНИЯ МЕТОДА АНАЛИЗА ИЕРАРХИЙ ДЛЯ
РЕШЕНИЯ ЗАДАЧИ ВЫБОРА АЛЬТЕРНАТИВ
1. Цель работы: исследовать применение аппарата метода анализа иерархий при
принятии решений по выбору альтернатив
2. Теоретическое введение
2.1. Общие понятия метода анализа иерархий
При принятии решений в сложной системе, состоящей из взаимосвязанных компонент
различного вида (ресурсы, желаемые исходы либо цели и т.д.), процесс функционирования
которой необходимо проанализировать, может быть применен метод анализа иерархий
(МАИ). Метод анализа иерархий сводит принятие решений в сложной системе к
последовательности попарных сравнений ее отдельных компонент.
Метод может быть применен для принятия решений при покупке оборудования,
планировании распределения энергии, вложениях в условиях неопределенности и т.д.
Для принятия решений в соответствии с МАИ выполняется декомпозиция сложной
системы (задачи) на отдельные еѐ компоненты (составляющие) и определяются отношения
между составляющими. В результате формируется модель системы (задачи), имеющая вид
иерархии. Вид иерархии предполагает наличие следующих уровней:
1) первый (верхний) уровень – одна глобальная (общая) цель принятия решений;
2) второй уровень – локальные подцели, полученные в результате декомпозиции глобальной
(общей) цели;
3) третий уровень – воздействия (управления), реализация которых в системе позволяет
достичь сформированных подцелей (решения, стратегии, приводящие к достижению
подцелей);
4) четвертый (нижний) уровень – исходы, представляющие собой результаты реализации
решений в системе (стратегий).
После формирования иерархии «цель – подцели – решения - результаты» реализуется
сравнение отдельных компонент уровней иерархии между собой. В результате сравнения
отдельных компонент системы между собой определяется относительная степень
интенсивности взаимодействия элементов в иерархии.
Упорядоченным множеством называется множество X с отношением порядка(не
хуже), если отношение удовлетворяет законам рефлексивности, антисимметричности и
транзитивности. Если решения x1 и x2 связаны отношением (т.е. x1 x2 ), то x1 не хуже x2 (т.е. x1
лучше, чем x2 , либо x1 и x2 эквивалентны). Тогда x1 предшествует x2 (если x1 x2 ) в цепочке
решений. Свойства отношения (не хуже):
а) рефлексивность: для всех xi , xi xi (т.е. xi не может быть хуже самого себя);
б) антисимметричность: если x1 x2 и x2 x1 , то x2 = x1 ;
в) транзитивность: если x1 x2 и x2 x3 , то x1 x3 .
Отношение - отношение «лучше».
Тогда, если x1 x2 , то x1 лучше x2 . Решение x1 доминирует решение x2 , если x1 x2 , x1 xi x2
невозможно ни для какого xi .
Подмножество X ′упорядоченного множества X называется ограниченным сверху, если
существует элемент xi ∈X такой, что xi x j для любого x j ∈X ′.Элемент xi - верхняя граница
множества (подмножества) X ′.
Способ задания иерархии. Обозначения:
X

{ x
j
| x
i
покрывает
x
j
} , т.е.
X– те
решения x j , которые покрываются рассматриваемым решением
x
i
;
X
+
=
{ x
j
| x
j
покрывает
74
xi } , таким образом, X - множество тех элементов x j , которые покрывают элемент xi
(рассматриваемый элемент xi ). При этом xi ∈X и x j ∈X , где X - упорядоченное множество.
Определение иерархии:
1) H – упорядоченное множество (частично упорядоченное множество) с наибольшим
элементом b (т.е. упорядоченное множество H ограничено сверху элементом b );
2) выполнено разбиение
множества
элементов H
на
подмножества элементов
L
k
,
k1,2,...,h ,
при
этом
L
1

{
b
}
,
таким образом, Lk
-
подмножество элементов,
соответствующих k-му уровню иерархии,
первый уровень состоит из одного элемента
b
( L1 {b} );
3) если x ∈L , то
XL
k

1
,
где
X
–
это элементы (k+1)-го
уровня (множества
L
k +1
),
i
k
покрываемые элементом xi ;
4) если x ∈L , то
XL
k

1
,
где
X
–
это элементы (k-1)-го
уровня (множества
L
k
1
),
i
k
которые покрывают элемент xi .
Функция приоритета.
Если
X

{ x
j
| x
i
покрывает x
j
}
,
то может быть определена
функция wx ( x j ) , такая, что wx : X → [ 0,1] , т.е. отображающая элементы x j множества X на
интервал [0,1] . Таким образом, каждому элементу x j ∈ X ставится в соответствие весовая
функция wx ( x j ) → [ 0,1] , при этом выполняется условие: ∑ wx ( x j ) 1 . Т.е. wx ( x j ) – вес,
x j∈X
который ставится в соответствие элементу x j ∈ X .
Пример построения иерархии элементов в задаче выбора сетевого оборудования.
Элементами множества H являются: 1) цель (выбор оборудования); 2) факторы, влияющие на
цель (наименование характеристик моделей сетевого оборудования, на основе анализа
значений которых выполняется выбор); 3) модели сетевого оборудования, среди которых
будет выполняться выбор эффективного.
Тогда H { оборудование, производительность процессора,
объем
ОЗУ,
производительность сети, цена, ремонтопригодность, модель 1, модель 2, модель 3} .
Формирование иерархии элементов множества
H на подмножества L1 , L2 , L3 (т.е. k 3 );
H . Реализуется разбиение множества
где L {оборудование}, L {
1 2
производительность процессора, объем ОЗУ, производительность сети, цена,
ремонтопригодность }, L3 { модель 1, модель 2, модель 3}. Вид иерархии цели,
характеристик, решений представлен на Рис.1.
Рисунок 1.– Вид иерархии уровней для задачи выбора оборудования
Если x1 = оборудование и при этом x1 ∈L1 , то X L2 .
Если xi = Модель 1, а при этом xi ∈L3 , то X + = L2 .
75
Определение весовой функции wx для элемента xi = оборудование. Эта функция ставит
в соответствие характеристикам оборудования (элементам L2 ) значения из отрезка [0,1] и
определяет приоритет характеристик относительно цели – «выбора оборудования».
Пример определения значений wx ( x j ) следующий (где x j ∈ X )
Wоборудование (производительность процессора) 0,3;
Wоборудование (объем ОЗУ) 0,2 ;
Wоборудование (производительность сети) 0,2;
Wоборудование (цена) 0,2 ;
Wоборудование ( релоктопригодность) 0,1;
При этом ∑ Wоборудован ие ( x j ) 1 ;
x j∈X
Т.е. характеристика «Производительность процессора» имеет 30% –ое значение при
выборе оборудования, характеристика «объем ОЗУ» имеет 20% –ое значение при выборе
оборудования и т.д.
Понятие полной иерархии предполагает, что иерархия называется полной, если для
всех x

L
k
множество
XL
(k 2,...,h) . В рассматриваемом случае иерархия является
k1
полной.
Свойства элементов уровней иерархии. Упрощенный вид иерархии уровней для
принятия решений следующий: цели (общая цель функционирования системы, общая цель
принятия решения); критерии, раскрывающие цели (характеристики цели); виды деятельности
(решения), обеспечивающие достижение целей; характеристики видов деятельности.
С точки зрения анализа общей цели выполняется выбор видов деятельности,
обеспечивающих достижение цели с точки зрения различных критериев. Т.е. критерии – это
свойства (характеристики) цели, реализация которых (реализация свойств цели)
обеспечивается тем или иным видом деятельности.
Возможен также расширенный подход к построению иерархии уровней,
предусматривающий определение: 1) цели системы; 2) подцелей системы; 3) критериев,
раскрывающих цель и подцели (свойств, характеристик цели либо подцелей); 4) Компонент
системы, обеспечивающих достижение цели; 5) локальные цели компонент вышестоящего (4-
го) уровня; 6) виды деятельности (сценарии, решения), обеспечивающие достижение
локальных целей компонент системы, деятельность которых приводит к достижению общей
цели.
Стандартный подход предполагает задание трех уровней иерархии:
1) нижний уровень – виды деятельности (т.е. альтернативы, решения);
2) второй уровень – характеристики видов деятельности (видов действий);
3) верхний уровень – общая цель функционирования системы.
Пример. Нижний уровень – различные маршруты движения транспорта между двумя
пунктами (виды деятельности), второй уровень – характеристики видов деятельности (время
следования, сужения, выбоины, безопасность и т.д.), верхний уровень – общая цель – выбор
эффективного маршрута.
Таким образом, формируемая иерархия является моделью системы, в которой
реализуется принятие решений.
В общем виде задача принятия решений – это определение видов деятельность. В общем
виде действия по определению видов деятельности, наиболее эффективных с точки зрения
реализации общей цели, следующие:
1) задание важности характеристик видов деятельности относительно общей цели (важность
критериев, используемых для оценки решений с точки зрения достижения общей цели);
2) для каждой характеристики деятельности определяется степень влияния соответствующего
вида деятельности на эту характеристику, т.е. степень соответствия вида деятельности
определенной на втором уровне ее характеристике (т.е. в какой степени данный вид
деятельности предполагает реализацию данной характеристики).
76
В результате определяется степень обеспечения видом деятельности рассматриваемой
общей цели.
Степень влияния элементов одного уровня на один элемент другого (вышестоящего
уровня) представляет собой важность каждого элемента нижнего уровня для одного
рассматриваемого элемента верхнего уровня (т.е. приоритет элемента нижнего уровня для
соответствующего элемента верхнего уровня). Для определения приоритетов влияния j-ых
элементов (k+1)-го уровня на i-ый элемент k-го уровня реализуются следующие действия:
1) выполняется сравнение (попарное) элементов (k+1)-го уровня ( j 1,nk1 ) по степени их
влияния на i-ый элемент k-го уровня; в результате будет сформирована матрица суждений о
степенях влияния;
2) определяется собственный вектор и собственное значение сформированной матрицы
парных сравнений; собственный вектор обеспечивает упорядочивание приоритетов,
собственное значение является мерой согласованности суждений.
Если характеристика x j (k+1)-го уровня важнее характеристики xi того же уровня, то
степень важности определяется по таблице (матрице) парных уравнений. Т.е., если
альтернатива x j (k+1)-го уровня реализует некоторое свойство (критерий) с
предшествующего уровня в большей степени, чем альтернатива xi , то вес w j альтернативы
x j имеет большее значение, чем вес wi альтернативы xi . А значения wi и w j соответствующих
альтернатив xi и x j определяются на основе матрицы А парных сравнений
альтернатив (задаются в матрице парных сравнений альтернатив). Матрица парных сравнений
А предполагает, что элемент aij равен степени превышения важности альтернативы xi над
альтернативой x j для некоторого рассматриваемого свойства. При формировании матрицы
парных сравнений должно быть выполнено условие ее согласованности (условие
согласованности оценок сравнений).
Пример матрицы парных сравнений для трех альтернатив. Альтернативы xi ( i 1,3 )
представляют собой модели оборудования, матрица парных сравнений предполагает
определение (задание) степени превосходства одной альтернативы xi над альтернативой x j с
точки зрения реализации критерия (свойства) «производительность оборудования»).
Если x1 3x2 , x1 6 x3 , тогда 3x2 6 x3 , x2 2 x3 , x3 1 / 2x2 .
Т.е. в альтернативе x2 (модель оборудования x2 ) рассматриваемое свойство (критерий)
«производительность оборудования» в 2 раза превышает этот же критерий в альтернативе x3 .
В итоге матрица парных сравнений реализации рассматриваемого свойства (критерия) в
альтернативах xi ( i 1,3 ) имеет вид:
A x1
x 2
x3
x
1
x
2
x
3
1
2
6
1 / 2
1
2
1 / 6
1 / 2
1
.
Если матрица A сформирована, то необходимо выполнить проверку согласованности
оценок парных сравнений (проверить согласованность матрицы A ). Если условие
согласованности выполняется, то сформированная матрица A может быть использована для
расчета приоритетов (весов) wi соответствующих альтернатив xi . Если матрица A не
согласована, то значения элементов aij этой матрицы должны быть изменены. Для проверки
согласованности матрицы A на ее основе должен быть вычислен вектор приоритетов влияния
wij ( j1,3) j-ых компонент рассматриваемого уровня иерархии на i-ый компонент
предшествующего уровня (вычисляются веса wij текущих j-ых элементов). Таким образом,
77
должно быть определено значение wik jk1 приоритета влияния j-ой компоненты (k+1)-го
уровня на i-ый элемент k-го уровня, в итоге определяется вектор собственных значений W
матрицы A - вектор приоритетов.
С математической точки зрения – это вычисление главного собственного вектора
матрицы A , который после нормализации становится вектором приоритетов (собственный
вектор матрицы A есть вектор приоритетов).
Методы получения собственного вектора матрицы A сформулированы в приложении
A .
2.2. Метод получения грубой оценки согласованности
Имеем матрицу парных сравнений A в виде:
A
a
11
a12
...
a
1n
a
21
a22
...
a
2n
...
a
n1
an2
...
a
nn
В результате реализации одного из методов получен вектор собственных значений w
матрицы А в виде:
w
1
w
w
2
.
...
w
n
На основе вектора w необходимо вычислить вектор w’ следующим образом:
w Aw
(произведение матрицы А на вектор w). Далее на основе вектора w '
определяется вектор w''
следующим образом: w'' [i] w' [i] / w[i] , где i
1, n
. Значение

m ax
(собственное
значение
матрицы A ) на основе вектора w’’ будет вычислено следующим образом:
n
max w[ i ] / n .
i1
Если
m ax n , то матрица парных сравнений значений характеристик альтернатив
является хорошо согласованной. Если n
m ax имеет большое значение, то степень
согласования низкая и должна быть переопределена матрица парных сравнений A .
Степень согласованности может быть выражена величиной (
m ax n) /(n1) , которая
называется индексом согласованности (ИС). Если значение (
m ax n) /(n1) приближается к
0, то согласованность достаточная.
Группа экспертов формирует суждения об относительной важности объектов (действий),
всего n объектов (действий). В итоге реализации метода необходимо количественно
интерпретировать суждения по всем объектам (совместно количественно интерпретировать
суждения по всем объектам). Таким образом, из количественных суждений, ассоциированных
с каждой из пар объектов, реализуется формирование весов, ассоциированных с отдельными
объектами (вес каждого объекта отражает количественные суждения всей группы экспертов).
Обозначения: x1 , x2 , …, xn – совокупность объектов (действий). Для пары ( xi , x j )
определяется элемент aij матрицы парных сравнений A , соответствующий степени важности
элемента xi относительно элемента x j .
78
Элементы aij определяются следующим образом:
1) если aij
, то a ji 1 /

,
 0 ;
2) если xi и x j имеют одинаковую важность, то aij1 и a ji 1 .
Тогда матрица суждений (парных сравнений) A примет вид:
1
a
...
a
12
1n
A

1 /
a
12
1
...
a
2n
.
...
1 / a
2n
...
1
1 / a1n
На основе сформированной матрицы A необходимо определить числовые веса w1 , w2 ,...,
wn , которые соответствовали бы каждому действию (объекту). Т.е. реализовать
способ получения весов wi на основе суждений aij . Результатом является определение вектора
приоритетов ( w1 , w2 ,..., wn ). Определение вектора приоритетов действия (решений,
альтернатив) реализуется путем нахождения собственных векторов матриц A парных
сравнений для каждого уровня (данный подход введен в рассмотрение выше).
После того, как для каждого вида деятельности сформированы приоритеты с точки
зрения удовлетворения характеристик (критериев), выполняется определение приоритетов
характеристик (критериев) относительно общей цели (т.е. как рассматриваемые свойства
будут обеспечивать общую цель).
Для получения общей характеристики вида деятельности (например, i-го вида
деятельности) по каждому критерию необходимо:
1) умножить вес оценки i-го вида деятельности по некоторому j-ому критерию на вес этого
критерия в общей цели принятия решения (таким образом, wij2 w1j , где wij2 – вес оценки i-го
вида деятельности относительно j-ой характеристики второго уровня иерархии, w1j – вес j-ой
характеристики относительно общей цели системы (первого уровня иерархии); всего должно
быть получено
m
значений
wij2 w1j , где
m
– количество критериев(характеристик) видов
деятельности;
2) полученные значения
wij2 w1j
для каждого i-го
вида деятельности сложить по всем j-ой
критериям ( j 1, m) ( критериям, характеризующим общую цель принятия решений), тогда
общая характеристика i-го вида деятельности Di будет определена следующим образом:
m
Dw2 w1 .
i ij j
Понятно, что тот i’-ый вид деятельности, который гарантирует максимальное значение
оценки Di , будет являться эффективным. Условие определения эффективного вида
деятельности i’ имеет следующий вид:
m
i arg m
ax
Di arg m
ax
w
ij2

w
1j
.
i1,n
i1,n j1
Пример применения метода анализа иерархий для реализации принятия решения по
выбору вида сетевого оборудования, приобретаемого компанией.
79
Т.к. общая цель реализации процедуры принятия решения состоит в выборе
эффективного оборудования, то верхний уровень иерархии принятия решений содержит узел
«эффективное оборудование» (это и будет общая цель в иерархии).
Второй уровень представляет собой критерии (характеристики), в соответствии с
которыми выполняется определение эффективного решения по выбору оборудования (т.е.
критерии, определяющие цель выбора оборудования). Множество характеристик (критериев)
определено следующим образом: {производительность процессора, скорость передачи
данных, объем памяти для хранения пакетов, цена оборудования, ремонтопригодность, срок
гарантии}.
В сокращенном виде множество характеристик оборудования представлено в
следующем виде: {производительность, скорость, объем памяти, цена, ремонтопригодность,
гарантия}.
Выбор осуществляется среди трех единиц оборудования. Обозначим их как O1 , O2 , O3
соответственно. Тогда иерархия «цель – критерии - решения» представлена на Рис.2.
Рисунок 2 – Вид иерархии при принятии решений о выборе оборудования.
Для характеристик, определяющих (соответствующих) эффективному оборудованию
сформирована матрица парных сравнений A1 . Элементы этой матрицы соответствуют степени
важности какой-либо из характеристик оборудования по сравнению с другими
характеристиками с точки зрения общей цели принятия решений.
Вид матрицы парных сравнений A1 (важность характеристики относительно цели)
следующий:
производительность
скорость
объем
цена
ремонто
гарантия
памяти
пригодность
производительность
1
4
3
1
3
4
A
1

скорость
1 / 4
1
7
3
1 / 5
1
объем памяти
1 / 3
1 / 7
1
1 / 5
1 / 5
1 / 6
цена
1
1 / 3
5
1
1
1 / 3
ремонтопригодность
1 / 3
5
5
1
1
3
гарантия
1 / 4
1
6
3
1 / 3
1
С использованием одного из приведенных в Приложении А методов определения
собственного вектора матрицы A (использован первый метод) получены следующие значения
w1j элементов вектора приоритетов W 1 ( j = 1,m ) : W 1 = ( 0.32;0.14;0.03;0.13;0.24;0.14 ) .
80
В этом случае вес w11 0.32 соответствует производительности процессора в общей цели
выбора оборудования, вес w12 0.14 – скорости передачи данных в общей цели, вес w31 0.03
– объему памяти в общей цели и т.д.
Тогда собст венное значение матрицы A1 , определя ющее согласов анность
сформированных суждений определено равным 7.49 ( λ1max = 7.49 ) , а индекс согласованности
суждений определен равным 0.3 ( ИС1 0,3 ).
Для уровня иерархии видов оборудования сформированы матрицы парных сравнений по
каждой из характеристик A2j ( j1, m) . Значения ail элементов этих матриц определяют
степень эффективности какого-либо i го типа оборудования по сравнению с другими (l-ми)
типами для соответствующей j ой характеристики (критерия).
Вид матриц A2j и вид собственных векторов w2j соответствующих матриц,
коэффициенты согласованности имеют следующий вид:
Производительность:
O1
O2
O3
w2
( 0.16;0.59;0.25 ),
A
2
= O
1
1
1 / 3
1 / 2
;
1
max
3.05;
1
O2
3
1
3
ИС 0.025;
O3
2
1 / 3
1
Скорость передачи данных:
A2=O1
2 O2
O3
O1
O
2
O3
1
1
1
1
1
1
1
1
1
w22 ( 0.33;0.33;0.33 ),
;
max 3.0;
ИС0;
Объем памяти:
= O
1
O1
O
2
O
3
A
2
1
5
1
3
O2
1 / 5
1
1 / 5
O3
1
5
1
Цена оборудования:
w32 ( 0.45;0.09;0.46 ),
;
max 3.0;
ИС0;
= O
1
O1
O
2
O
3
w
42
 ( 0.77;0.05;0.17 ),
A
2
1
9
7
;
max
3.21;
4
O2
1 / 9
1
1 / 5
ИС 0.105;
O3
1 / 7
5
1
Ремонтопригодность:
O1
O
2
O
3
w2
( 0.25;0.5;0.25 ),
A
2
= O
1
1
1 / 2
1
;
5
max
3.21;
5
O2
2
1
2
ИС0;
O3
1
1 / 2
1
Срок гарантии
O
1
O
2
O3
w2
( 0.69;0.09;0.22 ),
A
2
= O
1
1
6
4
;
6
max
3.05;
6
O2
1 / 6
1
1 / 3
ИС 0.025.
O3
1 / 4
3
1
В соответствии с полученными векторами w2j ( j1, m) для каждого вида оборудования
Oi (i1,3) формируется свой вектор значений всех характеристик следующим образом
( j 1, m) :
w2 = ( 0.16;0.33;0.45;0.77;0.25;0.69 );
o1
w2 = ( 0.59;0.33;0.09;0.05;0.5;0.09 );
o2
λ1max
81
w2 = ( 0.25;0.33;0.46;0.17;0.25;0.22 ).
o3
Так как вектора w1 и w2
(i
1,3) сформированы, то может быть получена оценка
D
i
o
i
каждого вида оборудования по формуле: m
Dw2 w1 .
i ij j
Полученные значения Di следующие: D1 = 0.37; D2 = 0.38; D3 = 0.25 . Отсюда следует, что
второй вид оборудования наиболее предпочтителен.
3. Программа выполнения работы
3.1. Сформировать следующие матрицы:
а) парных сравнений влияния характеристик альтернатив (решений) на общую цель принятия
решений (матрицу А1);
б) парных сравнений наличия рассматриваемых свойств (характеристик) у предлагаемых к
анализу решений x j – матрицы A2j (где j = 1,m , m – количество критериев (свойств,
характеристик) рассматриваемых альтернатив);
3.2. Реализовать процедуру, которая используя заданный в варианте метод, определяет вектор
собственных значений W каждой из матриц парных сравнений, вычисляет собственное
значение матрицы λmax и индекс согласованности (ИС) оценок в ней.
3.3. Проверить выполнение условия согласованности оценок в каждой из матриц парных
сравнений на каждом уровне. В случае плохой согласованности повторить шаги 1 и 2.
3.4. Разработать процедуру, которая на основе векторов собственных значений w2j матриц A2j (
j = 1,m , количество элементов в каждом из векторов равно количеству рассматриваемых
решений (альтернатив), т.е. n) для каждого из решений сформировать вектор
Wi2
весовых
коэффициентов
wi2 ,
каждый
из
которых
соответствует
наличию
j-ой
характеристики
(свойства, критерия) у соответствующего i-го решения (количество элементов в каждом из
этих векторов равно количеству свойств решений, влияющих на общую цель принятия
решений, т.е. m);
3.5. Разработать процедуру, которая на основе векторов весовых коэффициентов на первом
уровне – W , на втором уровне –
W 2
( j =
) выполняет расчет оценок D
для каждого
1,m
1
j
i
решения, эта же процедура реализует
определение на основе значений
Di ( i
1,n
)
эффективного решения x*i .
4. Варианты заданий
Вариант 1. У студентов в процессе обучения возникает необходимость определения
предмета, который они хотели бы изучать по выбору. Характеристиками (критериями),
соответствующими свойствам предметов, на основе которых выполняется выбор (влияющих
на выбор предмета) являются: фундаментальные знания, которые содержит преподаваемый
предмет, соответствие современному уровню развития науки в данной области, возможность
использования в профессиональной деятельности, симпатии к преподавателю. Для анализа и
выбора могут быть предложены следующие предметы: теория принятия решений, теория
алгоритмов, теория вероятностей и математическая статистика, теория информационных
процессов, технологии обработки информации, технологии программирования. Для
реализации выбора необходимо сформировать требуемые матрицы парных сравнений и
реализовать процедуру принятия решений. При этом для определения значений элементов
82
собственных векторов матриц парных сравнений использовать первый из предложенных в
Приложении А методов.
Вариант 2. В процессе реализации дипломного или курсового проектов возникает
необходимость в выборе языка программирования. (цель принятия решений– выбор языка
программирования для реализации проекта). Характеристики, соответствующие свойствам
альтернатив (решений), влияющие на цель принятия решений: наличие базовых знаний
синтаксиса языка, соответствие языка современному уровню развития технологий
программирования, сложность синтаксиса, имеющееся время на реализацию проекта. Для
реализации выбора необходимо сформировать требуемые матрицы парных сравнений и
реализовать процедуру принятия решений. При этом для определения значений элементов
собственных векторов матриц парных сравнений использовать второй из предложенных в
Приложении А методов.
Вариант 3. В процессе дипломного проектирования возникает необходимость выбора
темы дипломного проекта. (дипломный руководитель предлагает несколько тем на выбор).
Цель принятия решений состоит в выборе темы для дипломного проектирования из
предлагаемого перечня. Характеристиками (критериями) , соответствующими свойствам
решений, являются: сложность материала, положенного в основу темы дипломного проект;
наличие знаний по материалу, на основе которого реализуется дипломный проект;
возможность использования знаний, полученных при дипломном проектировании по
выбранной теме, в дальнейшей деятельности; наличие свободного времени для реализации
выбранной темы дипломного проекта. Для реализации выбора необходимо сформировать
требуемые матрицы парных сравнений и реализовать процедуру принятия решений. При этом
для определения значений элементов собственных векторов матриц парных сравнений
использовать третий из предложенных в Приложении А методов.
5. Контрольные вопросы
5.1. Какой вид с точки зрения иерархически упорядоченных уровней имеет модель системы в
МАИ (какие уровни образуют иерархию с точки зрения модели системы в МАИ)?
5. 2. Какие виды отношений используются при определении иерархической модели системы в
МАИ (какие понятия используются при определении иерархии уровней в модели системы в
МАИ) ?
5. 3. Каким образом формализуется определение иерархии уровней в модели системы в МАИ?
5. 4. Что такое функция приоритета для элементов уровней и что она определяет (для
элементов каждого уровня) ?
5.5. Для чего используются матрицы парных сравнений на каждом уровне иерархической
модели системы в МАИ?
5. 6. В чем отличие в формировании матрицы парных сравнений А1 , формируемой на втором
уровне иерархии в модели системы, от матриц парных сравнений A2j ( j1, m) , формируемой
на третьем уровне иерархии модели системы?
5.7. Каким образом выполняется вычисление вектора собственных значений матрицы парных
сравнений?
5. 8. Каким образом выясняется согласованность оценок в матрицах парных сравнений
5. 9. Какие действия должны быть предприняты в случае плохой согласованности оценок в
матрицах парных сравнений?
5. 10. Каким образом на основе матриц парных сравнений могут быть получены весовые
коэффициенты для характеристик или решений соответственно на втором и третьем уровнях
иерархии?
5.11. В чем состоит процедура вычисления значения оценки эффективности каждой
альтернативы в МАИ?
5.12. В чем заключается обобщенный алгоритм принятия решений в МАИ?
83
ЛАБОРАТОРНАЯ РАБОТА №7
ИССЛЕДОВАНИЕ МЕТОДОВ ГРУППОВОГО ВЫБОРА РЕШЕНИЙ
1. Цель работы: исследовать способы определения эффективных решений при
групповом выборе.
2. Теоретическое введение
Имеется n различных бинарных отношений на множестве . Отношение
называется индивидуальным. Оно задает предпочтение i-го субъекта (ЛПР, эксперта).
Требуется сформировать отношение
, согласованное с отношениями
.
Отношение
называется групповым отношением.
Правило (система правил), описывающее способ построения группового отношения ,
исходя из
системы
индивидуальных
отношений
, называется
принципом
согласования отношений.
Обозначив через
способ (правило) отображения группы отношений
в
групповое
отношение
, имеем:
.
Отображение
– принцип
согласования. Разные отображения
могут быть использованы для определения отношения
.
Пример 1. Множество имеет вид: . Предпочтения трѐх экспертов
заданы следующими ранжированиями (т.е. элементы xi в упорядочены в
соответствии с рангами , при этом ), (т.е.
), ) (т.е. ). Определен принцип
отображения , предполагающий, что .
Правила согласования группы отношений с отношением могут быть
сформулированы довольно сложно.
Например: , если и .
Правило большинства.
Правило большинства – наиболее распространѐнный принцип согласования. Пусть
– индивидуальные отношения на . Обозначим через количество
индексов i ( i – индекс отношения), для которых . Тогда могут быть
сформированы два способа построения (определения) множества :
1)
2) , где и соответствующие обобщающие
отношения.
Отношения и называются мажоритарными отношениями.
Пример 2 определения обобщающего отношения .
, отношения задаются ранжированием в следующем виде:
, , .
,
,
,
,
Так как
, то
,
и
,
то
вид отношения :
. По аналогии рассуждения формируются для
.
В
результате имеем
.
Пример 3.
84
,
, , .
, , , , ,=> , , (
но не как следовало бы из рассуждений о транзитивности).
Таким образом, групповое отношение не является транзитивным, что не приемлемо,
если для задания формы отношений использованы ранговые шкалы. Так как групповое
отношение выражает некоторый согласованный признак, то оно должно индуцировать
отношение квазипорядка (некоторого порядка).
На основе анализа приведенных примеров видно, что правило большинства может
приводить как к транзитивным, так и к не транзитивным отношениям . Необходимо
сформировать условия, при которых индивидуальные отношения и мажоритарное
отношение являются линейными квазипорядками (т.е. обеспечивают упорядоченность
решений).
Рассмотрим множество . Существует 13 ранжирований (линейных
квазипорядков) этого множества: , , ,
, , , , ,
, , , ,
. Здесь знак «∼» обозначает неразличимость (эквивалентность) решений.
Далее при рассмотрении нумерация ранжирований является фиксированной. Через
обозначим количество субъектов (ЛПР, экспертов), которые придерживаются отношения
(ранжирования ). При этом .
В рассмотрение вводится подмножество таких элементов , для которых .
Подмножество , при этом , если , и , если .
Тогда множество называется совокупностью ранжирований.
Пусть имеется совокупность трех строгих ранжирований вида: , ,
, полученных друг из друга циклической перестановкой объектов (решений). Эта
совокупность ранжирований называется циклической. Каждое из упорядочений циклической
совокупности порождает остальные упорядочивания перестановкой первого элемента на
последнее место и перестановкой последнего элемента на первое место. Эти два элемента
называются циклическими. Например, упорядочивание порождает с циклическим объектом
(элементом) и упорядочивание с циклическим объектом . Рассмотрим
ранжирование вида: , , , каждое из которых
представляет из себя линейный квазипорядок (частичный порядок). Каждое из этих
ранжирований содержит в себе 2 класса объектов: эквивалентные и связанные с ними
доминирующие или доминируемые элементы.
Тогда линейный квазипорядок называется дихотомическим, им соответствующее
ранжирование состоит из 2-х классов (т.е., в частном случае, ранжирование состоит из 3-х
элементов, один из классов обязательно содержит один элемент). Дихотомическое
ранжирование называется однотипным, если их одноэлементные классы имеют один и тот же
номер. Тогда ранжирование и являются однотипными, а и
не являются однотипными.
То есть, необходимо охарактеризовать (определить условия) индивидуальные
отношения (наборы индивидуальных отношений), для которых хотя бы одно (т.е. построенное
с использованием одного из правил) мажоритарное отношение было транзитивно.
Для упрощения рассуждений может быть выполнен переход от множества к любому
его трехэлементному подмножеству (к трехэлементным подмножествам). Требуется
сформировать критерий допустимости множества ранжирований
85
Обобщенное понятие циклической совокупности строгих ранжирований формируется
следующим образом. Множество трех линейных квазипорядков (ранжирований) вида
называется циклическим, если оно удовлетворяет следующим
условиям:
а) если в одном из отношений объекты (элементы, решения) являются неразрывными,
тогда для циклических объектов остальных отношений имеет место строгое предпочтение;
б) все три отношения не могут быть однотипно дихотомическими.
Пример ранжирований, соответствующих условию а).
, , .
Пример ранжирований, соответствующих условию б).
, , .
Подмножество является допустимым, если при для и
для существует транзитивное мажоритарное отношение . В том случае, если
будет сформирована допустимая совокупность ранжирований , то
существует транзитивное мажоритарное отношение .
На основе рассмотренных свойств (признаков) циклических ранжирований может быть
сформировано условие допустимости совокупности ранжирований .
Теорема 1. Совокупность ранжирований является допустимой, когда она не включает
циклического множества (т.е. всякое циклическое множество недопустимо и не может
содержаться в ).
В качестве примера, комментирующего суть Теоремы 1, рассмотрим циклические
ранжирования следующего вида: . За каждое отношение
отдано одинаковое число голосов. Тогда , , но , следовательно,
не является транзитивным.
Пусть циклическое множество состоит из дихотомических ранжирований и в
соответствии с пунктом б) имеет следующий вид: , тогда
, , но , следовательно, отношение нетранзитивно.
В итоге получим, что правило большинства позволяет сформировать транзитивное
мажоритарное ранжирование только в том случае, если множество ранжирований
является допустимым, т.е. в него не могут входить циклические ранжирования. В итоге
правило большинства может быть применено в частном случае. Для общего случая (когда
отсутствуют ограничения на вид ранжирований) правило большинства не позволяет получить
транзитивное мажоритарное ранжирование .
Правило большинства может быть обобщено (т.е. применимо при построении
ранжирования в общем виде) в терминах расстояния между исходными отношениями
(ранжированиями).
На основе ранжирования может быть сформирована матрица парных сравнений
,где ,
k – индекс эксперта.
В том случае, если заданы два ранжирования и , тогда расстояние между этими
двумя ранжированиями будет определено согласно отношению:
86
Пусть дано множество ранжирований , тогда расстояние от некоторого
ранжирования до этого множества определяется следующим образом:
где – элемент матрицы соответствующий некоторому ранжированию
(произвольному ранжированию из множества ).
В случае рассмотрения отдельного элемента (соответствующего ранжированию
) может быть определено для него расстояние между и остальными ранжированиями
:
То есть
определяется для тех элементов
, соответствующих ранжированию ,
которые равны 1. Элемент
– коэффициент потерь (при этом
),
а матрица
называется матрицей потерь.
Ранжирование
, такое,
что
называется медианой множества
. Т.е. это такое ранжирование, которое с точки зрения расстояния является
«наиболее близким» ко всем ранжированиям
.
Для определения мажоритарного транзитивного ранжирования применим метод
Кемени, в котором при расчете элемента
, матрицы потерь
используются отличия
значений элементов
матриц соответствующих ранжирований
Алгоритм Кемени определения меридианы (ранжирования)
, которое будет являться
транзитивным, предполагает выполнение следующих шагов.
1 шаг.
Для
расчета значения элемента
матрицы
потерь
выполняется
идентификация такого ранжирования , для которого выполняется условие:
Тогда значение матрицы потерь определяется согласно отношению:
В итоге формируется матрица , соответствующая элементам .
После идентификации матрицы потерь требуется определить матрицу , на основе
которой в дальнейшем идентифицируются альтернативы, соответствующие удаляемым из
матрицы (и, соответственно из матрицы .
2 шаг. Определение матрицы :
87
, где
где – матрица, все элементы (кроме диагональных) равны 1.
3 шаг. В полученной матрице реализуется определение элемента .
Альтернативы (решения), определяющие строку и столбец элемента обозначаются и
соответственно (т.е. они размещаются в позиции и соответственно).
4 шаг. Полученные таким образом альтернативы размещаются в -ой и первой
позициях формируемого ранжирования . После этого реализуется удаление
соответствующих -ой строки и -го столбца.
Пример определения медианы для множества ранжирований .
Задано 4 эксперта и сформулированные ими ранжирования в следующем виде:
, , ,
Ранжированием соответствуют матрицы отношений следующего вида:
1 шаг. Определение матрицы потерь
. Имеем:
=> .
По аналогии:
=> .
Выполняя расчеты подобным образом, получим матрицу потерь в следующем виде:
2 шаг. Определение матрицы потерь :
Имеем матрицу в следующем виде:
88
3 шаг. Определение матрицы потерь .
В данном случае – это Тогда альтернативы в результирующем ранжировании
разметим следующим образом: .
Так как решения , исключены из рассмотрения, тогда должны быть
модифицированы матрицы путѐм исключения из них 3-го столбца и 1-ой строки. В
результате имеем:
1 шаг. Определение матрицы потерь. Матрица имеет вид:
2 шаг. Определение матрицы потерь . На основе матрицы формируем
матрицу в следующем виде:
Так как решения уже добавлены в ранжирование , то нас будет интересовать
решения . Соответственно рассматриваем элементы и . Т.к.
элемент , тогда на основе элемента определяем позиции в
ранжировании. Получаем (т.е. решение i во второй позиции в ) и (т.е.
решение i в третей позиции в ). Тогда результирующее ранжирование имеет вид:
.
3. Порядок выполнения работы
1. Разработать процедуру, реализующую формирование для заданных ранжирований
соответствующих им матриц отношений Ri.
2. Разработать процедуру формирования матрицы потерь Qn на основе сформированных
матрицы отношений Ri.
3. Разработать процедуру определения решений, включаемых в итоговое ранжирование.
4. Разработать процедуру модификации матриц отношений Ri путем исключения решений,
добавленных в формируемое итоговое ранжирование.
5. Разработать модуль, координирующий выполнение упомянутых выше процедур.
89
4. Варианты заданий.
Вариант 1. Выполнить определение итогового ранжирования R для исходных
ранжирований следующего вида:
R1=(x2, x4, x1, x3, x5, x8, x7, x6);
R2=(x1,x5,x4~x2,x6,x7~x8, x6);
R3=(x3,x4,x8~x7,x6,x5,x2, x1);
R4=(x7,x8,x3~x4,x6~x2,x1, x5);
R5=(x4,x8,x3~x7,x6~x1,x2, x5);
Вариант 2. Выполнить определение итогового ранжирования R для исходных
ранжирований следующего вида:
R1=(x2, x4, x1, x3, x5, x6);
R2=(x1,x5,x4~x2,x6, x3);
R3=(x3,x4~x6,x5,x2, x1);
R4=(x3~x4,x6~x2,x1, x5);
R4=(x3~x4,x6~x2,x1, x5);
R5=(x6~x4,x1~x2,x5, x3);
R6=(x3,x4,x6,x2,x1~x5);
R7=(x3, x4,x1~x2,x5, x6);
R8=(x3,x4,x6~x2,x1~x5);
Вариант 3. Выполнить определение итогового ранжирования R для исходных
ранжирований следующего вида:
R1=(x2, x4, x1, x3, x7,x5, x6);
R2=(x1~x7,x5,x4~x2,x6, x3);
R3=(x3,x4~x6,x5,x2~ x7, x1);
R4=(x3~x4,x6~x2,x1,x7,x5);
R4=(x3~x4,x6~x2,x1, x5~ x7);
R5=(x6~x4,x1~x2,x7,x5, x3);
R6=(x7,x3,x4,x6,x2,x1~x5);
R7=(x7~x3,x4,x6,x2,x1~x5);
5. Контрольные вопросы
1. В чем заключается постановка задачи группового выбора решений?
2. В каком виде представляются исходные отношения, формируемые группой экспертов?
3. В чем заключается правило большинства при построении мажоритарных отношений?
4. В чем состоит причина не выполнения свойства транзитивности для мажоритарного
отношения , обобщающие отношения экспертов?
5. Что из себя представляют дихотомические однотипные и разнотипные ранжирования?
6. Что представляет из себя медиана Кемени с точки зрения группового выбора?
7. Что такое матрица потерь и как она формируется?
8. Как формируются матрицы отношений на основе задаваемых ранжирований?
9. В чем состоит алгоритм формирования итогового ранжирования R?
90
Библиографический список
1. Петровский А.Б. Теория принятия решений./ А.Б. Петровский – М.: Издательский центр
"Академия", 2009.– 400 с.
2. Будаева А.А. Принятие решений: теория, технология, приложения. Учебное пособие. / А.А.
Будаева, В.О.Гроппен. – Владикавказ: Изд–во "Фламинго", 2010.– 184 с.
3. Фишберн П.К. Теория полезности для принятия решений./ П.К. Фишберн — М.: Наука,
1978– 353 с.
4. Кини Р.Л., Райфа Х. Принятие решений при многих критериях. Предпочтения и замещения.
— М.: Радио и связь, 1981.– 250 с.
5. Гладких Б.А. Методы оптимизации и исследования операций для бакалавров информатики.
Ч. III.Теория решений. Учебное пособие. – Томск: Изд–во НТЛ, 2012.– 280 с.
6. Турунтаев Л.П. Теория принятия решений. Учебное пособие./ Л.П. Турунтаев. – Томск:
Изд–во Томского ун–та систем управления и радиоэлектроники, 2003.– 222 с.
7. Лотов А.В. Многокритериальные задачи принятия решений./ А.В.Лотов, И.И.Поспелова.–
М.:Изд–во МГУ, 2008. – 198 с.
8. Подиновский В.В. Введение в теорию важности критериев в многокритериальных задачах
принятия решений. / В.В.Подиновский– М.: ФИЗМАТЛИТ, 2007 – 64 с.
9. Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериальных задач./
В.В. Подиновский, В.Д. Ногин– М.: Наука. Главная редакция физико-математической
литературы, 1982.— 256 с.
9. Ногин В.Д. Принятие решений в многокритериальной среде. Количественный подход./ В.Д.
Ногин– М.: ФИЗМАТЛИТ, 2002 – 144 с.
10. Саати Т. Принятие решений. Метод анализа иерархий. — М.: Радио и связь, 1993.
91
ПРИЛОЖЕНИЕ А
МЕТОДЫ ОПРЕДЕЛЕНИЯ СОБСТВЕННЫХ ВЕКТОРОВ МАТРИЦЫ
ПАРНЫХ СРАВНЕНИЙ A
Метод 1
1) Выполнить суммирование элементов каждой строки
2) Нормализовать каждую из полученных сумм путем ее деления на сумму всех
элементов
3) Полученные результаты в сумме должны давать единицу; первый элемент
результирующего вектора является приоритетом (весом) первого объекта, второй – второго и
т.д.
Метод 2
1) Разделить элементы каждого столбца на сумму элементов этого столбца
(нормализовать элементы каждого столбца)
2) Полученные элементы сложить для каждой строки (выполнить построчное
суммирование полученных нормализованных элементов)
3) Разделить каждую из полученных сумм на число элементов в строке (процесс
усреднения по нормализованным столбцам)
Метод 3
1) Выполнить суммирование элементов каждого столбца и определить величины,
обратные каждой из полученных сумм (обратная величина для рассматриваемого значения –
это результат деления единицы на само это значение)
2) Разделить каждую обратную величину на сумму всех обратных величин
(нормализация обратных величин с тем, чтобы их сумма была равна 1).